UVa 11694

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2741

题意：

在一个 n*n（n≤7）网格中，有些交叉点上有数字。你的任务是给每个格子画一条斜线（一共只有“”和“/”两种），
使得每个交叉点的数字等于和它相连的斜线条数，且这些斜线不会构成环。

分析：

深搜 + 剪枝，枚举当前位置的两种摆法，
当当前位置是最后一个能更新某个数值的位置时，判断该数值是否为0，
若不是，则递归返回。这样有四种情况可以剪枝。
具体实现见代码。

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cctype>
  4 
  5 const int UP = 7 + 5;
  6 const int dr[4] = {-1, 1, -1, 1}; //左上，右下，右上，左下
  7 const int dc[4] = {-1, 1, 1, -1};
  8 const int udr[2] = {0, 0}; //反斜杠和斜杠的上方坐标
  9 const int udc[2] = {0, 1};
 10 const int ddr[2] = {1, 1}; //反斜杠和斜杠的下方坐标
 11 const int ddc[2] = {1, 0};
 12 
 13 int n, N, finish, mark, vis[UP][UP];
 14 char grid[UP][UP], ans[UP][UP], edge[UP][UP][UP][UP];
 15 //ans[r][c] 与 grid[r][c], grid[r][c+1], grid[r+1][c], grid[r+1][c+1] 相关联
 16 //r与c的下标从1开始
 17 
 18 void renew(int r1, int c1, int r2, int c2){ //恢复状态
 19     if(isdigit(grid[r1][c1])) grid[r1][c1]++;
 20     if(isdigit(grid[r2][c2])) grid[r2][c2]++;
 21 }
 22 
 23 bool loop(int r, int c, int f){ //判断是否有环
 24     if(vis[r][c] == mark) return true;
 25     vis[r][c] = mark;
 26     for(int i = 0; i < 4; i++){
 27         if((i ^ 1) == f) continue; //i的相反方向是否等于f
 28         int fr = r + dr[i], fc = c + dc[i];
 29         if(edge[r][c][fr][fc] == 0) continue;
 30         if(loop(fr, fc, i)) return true;
 31     }
 32     return false;
 33 }
 34 
 35 bool dfs(int id){
 36     if(id == finish) return true;
 37     if(id % N == 0) return dfs(id + 1); //该位置不做考虑，只是下一个位置的过渡
 38     int r = id / N, c = id % N;
 39     int jr = r + udr[0], jc = c + udc[0]; //判断该位置的数字是否大于0所用
 40     for(int i = 0; i < 2; i++){
 41         int ufr = r + udr[i], ufc = c + udc[i];
 42         int dfr = r + ddr[i], dfc = c + ddc[i];
 43         if(isdigit(grid[ufr][ufc]) && grid[ufr][ufc] - 1 < '0') continue;
 44         if(isdigit(grid[dfr][dfc]) && grid[dfr][dfc] - 1 < '0') continue;
 45         if(isdigit(grid[ufr][ufc])) grid[ufr][ufc]--;
 46         if(isdigit(grid[dfr][dfc])) grid[dfr][dfc]--;
 47         if(grid[jr][jc] > '0'){ //剪枝1
 48             renew(ufr, ufc, dfr, dfc);
 49             continue;
 50         }
 51         if(r == n){ //剪枝2
 52             int sr = r + ddr[1], sc = c + ddc[1];
 53             if(grid[sr][sc] > '0'){
 54                 renew(ufr, ufc, dfr, dfc);
 55                 continue;
 56             }
 57         }
 58         if(c == n){ //剪枝3
 59             int sr = r + udr[1], sc = c + udc[1];
 60             if(grid[sr][sc] > '0'){
 61                 renew(ufr, ufc, dfr, dfc);
 62                 continue;
 63             }
 64         }
 65         if(r == n && c == n){ //剪枝4
 66             int sr = r + ddr[0], sc = c + ddc[0];
 67             if(grid[sr][sc] > '0'){
 68                 renew(ufr, ufc, dfr, dfc);
 69                 continue;
 70             }
 71         }
 72         ans[r][c] = i;
 73         edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 1;
 74         mark++;
 75         if(loop(dfr, dfc, -1)){
 76             edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 0;
 77             renew(ufr, ufc, dfr, dfc);
 78             continue;
 79         }
 80         if(dfs(id + 1)) return true;
 81         edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 0;
 82         renew(ufr, ufc, dfr, dfc);
 83     }
 84     return false;
 85 }
 86 
 87 int main(){
 88     int T;
 89     scanf("%d", &T);
 90     while(T--){
 91         scanf("%d", &n);
 92         N = n + 1;
 93         for(int r = 1; r <= N; r++) scanf("%s", grid[r] + 1);
 94         memset(vis, 0, sizeof(vis));
 95         memset(edge, 0, sizeof(edge));
 96         mark = 1;
 97         finish = N * N;
 98         dfs(N + 1);
 99         for(int r = 1; r <= n; r++){
100             for(int c = 1; c <= n; c++){
101                 if(ans[r][c] == 0) printf("\");
102                 else printf("/");
103             }
104             printf("
");
105         }
106     }
107     return 0;
108 }