问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1629思路:
这题如果想通了，就是一水题呵呵，不亚于PKU 1000的'A+B Problem'
该题要求输出在填满words之后grid中剩余的字符，并且告诉我们一定存在解
最简单的办法就是对A-Z的字符进行计数，然后输出
现在，我们将题目的要求改变一下，找出所有可能的填满方案（更具挑战性）
这可以通过DFS来解决，代码如下:
通过调用solve(0)即可获得所有的方案
这里，set(x, y, index, ct)是找出对于words[index]的所有可能填充
1 void
2 set(int x, int y, int index, int ct)
3 {
4 int i, tx, ty;
5 visited[x][y] = index+1;
6 if(ct+1 == words_len[index]) {
7 solve(index+1);
8 visited[x][y] = 0;
9 return;
10 }
11 for(i=0; i<4; i++) {
12 tx = x + dx[i];
13 ty = y + dy[i];
14 if(is_valid(tx, ty) && !visited[tx][ty] && grid[tx][ty]==words[index][ct+1])
15 set(tx, ty, index, ct+1);
16 }
17 visited[x][y] = 0;
18 }
19
20 void
21 solve(int index)
22 {
23 int i, j;
24 if(index == p) {
25 for(i=0; i<n; i++) {
26 for(j=0; j<m; j++) {
27 printf("%d\t", visited[i][j]);
28 }
29 printf("\n");
30 }
31 return;
32 }
33 char c = words[index][0];
34 for(i=0; i<n; i++) {
35 for(j=0; j<m; j++) {
36 if(grid[i][j]==c && !visited[i][j])
37 set(i, j, index, 0);
38 }
39 }
40 }