【题目链接】
http://poj.org/problem?id=2676
【算法】
深度优先搜索
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; struct info { int x,y; } pos[110]; int i,j,len,T; char mp[10][10]; bool row[10][10],col[10][10],grid[10][10]; bool solved; inline int getpos(int x,int y) { return (x - 1) / 3 * 3 + (y - 1) / 3 + 1; } inline void dfs(int dep) { int i; if (dep > len) { solved = true; return; } for (i = 1; i <= 9; i++) { if (!row[pos[dep].x][i] && !col[pos[dep].y][i] && !grid[getpos(pos[dep].x,pos[dep].y)][i]) { mp[pos[dep].x][pos[dep].y] = i + '0'; row[pos[dep].x][i] = true; col[pos[dep].y][i] = true; grid[getpos(pos[dep].x,pos[dep].y)][i] = true; dfs(dep+1); if (solved) return; row[pos[dep].x][i] = false; col[pos[dep].y][i] = false; grid[getpos(pos[dep].x,pos[dep].y)][i] = false; } } } int main() { scanf("%d",&T); getchar(); while (T--) { solved = false; memset(row,false,sizeof(row)); memset(col,false,sizeof(col)); memset(grid,false,sizeof(grid)); len = 0; for (i = 1; i <= 9; i++) { for (j = 1; j <= 9; j++) { mp[i][j] = getchar(); if (mp[i][j] == '0') pos[++len] = (info){i,j}; else { row[i][mp[i][j]-'0'] = true; col[j][mp[i][j]-'0'] = true; grid[getpos(i,j)][mp[i][j]-'0'] = true; } } getchar(); } dfs(1); for (i = 1; i <= 9; i++) { for (j = 1; j <= 9; j++) { printf("%c",mp[i][j]); } printf(" "); } } return 0; }