问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2676思路:
深度搜索
纯粹按照题意进行搜索，1532MS...额...就快TLE了呵呵
据discussion说，倒过来搜索时间会相当快
代码:
1 #define MAX_LEN 10
2 char table[MAX_LEN][MAX_LEN];
3 int flag;
4
5 int
6 is_available(int x, int y, char ch)
7 {
8 int j, k, small_x, small_y;
9 for(j=0; j<9; j++) /* row */
10 if(table[x][j]==ch)
11 return 0;
12 for(k=0; k<9; k++) /* column */
13 if(table[k][y]==ch)
14 return 0;
15 small_x = x/3;
16 small_y = y/3;
17 for(j=small_x*3; j<(small_x+1)*3; j++)
18 for(k=small_y*3; k<(small_y+1)*3; k++)
19 if(table[j][k]==ch)
20 return 0;
21 return 1;
22 }
23
24 void
25 dfs(int x, int y)
26 {
27 int i, j, nx, ny;
28 if(flag)
29 return;
30 if(x==9){
31 if(!flag) {
32 for(j=0; j<9; j++)
33 printf("%s\n", table[j]);
34 flag = 1;
35 }
36 return;
37 }
38 if(y==8) {
39 nx = x+1;
40 ny = 0;
41 } else {
42 nx = x;
43 ny = y+1;
44 }
45 if(table[x][y] == '0') {
46 for(i=1; i<=9; i++) {
47 if(is_available(x, y, i+'0')) {
48 table[x][y] = i+'0';
49 dfs(nx, ny);
50 table[x][y] = '0';
51 }
52 }
53 } else
54 dfs(nx, ny);
55 }
更好的解题代码见:
http://blog.csdn.net/logic_nut/archive/2009/08/09/4428996.aspx