問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1629思路:
這題如果想通了，就是一水題呵呵，不亞于PKU 1000的'A+B Problem'
該題要求輸出在填滿words之后grid中剩余的字符，并且告訴我們一定存在解
最簡(jiǎn)單的辦法就是對(duì)A-Z的字符進(jìn)行計(jì)數(shù)，然后輸出
現(xiàn)在，我們將題目的要求改變一下，找出所有可能的填滿方案（更具挑戰(zhàn)性）
這可以通過(guò)DFS來(lái)解決，代碼如下:
通過(guò)調(diào)用solve(0)即可獲得所有的方案
這里，set(x, y, index, ct)是找出對(duì)于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 }