UVA11694-Gokigen Naname（DFS进阶）

Problem UVA11694-Gokigen Naname

Accept: 76 Submit: 586
Time Limit: 10000 mSec

Problem Description

Input

The ﬁrst line of the input ﬁle contains an integer N (N < 25) which denotes the total number of test cases. The description of each test case is given below: The ﬁrst line of each test case contains a single integer n (2 ≤ n ≤ 7), the number of cells along each of the sides in the square grid. Then follow n+1 lines containing the contents of the intersections of the grid cells. Each such line will contain a string of n + 1 characters, either a digit between 0 and 4, inclusive, or a period (‘.’) indicating that there is no number at this intersection (arbitrarily many lines may connect to it).

Output

For each test case print n lines, each line containing exactly n characters. Each character should either be a slash or a backslash, denoting how the corresponding grid cell is ﬁlled.

Sample Input

2
3
1.1.
...0
.3..
..2.
5
.21...
..33.0
......
..33..
0..33.
....11

Sample Output

//
\
//
/\//
//\
\//
/\/
///\

题解：我感觉这个题挺难的，DFS的思路还比较直接，但是维护哪些东西比较迷茫。首先肯定有一个原图，然后要维护一下各点目前已经连了几条边，最关键的是要维护每个节点最多还能连几条边（用于剪枝）。判环的问题丢给并查集。DFS的时候从上到下，从左到右，每次连一条边更新维护的东西，要更新的东西比较多，回溯的时候别漏了。这里的并查集有必要提一句，这里不能路径压缩，因为回溯时是一种类似删除节点的操作，简单画个图就能发现如果只在回溯时修改当前节点的父节点为原来的父节点是不对的。因此这里不路径压缩，并查集基本上就是个链表的作用。剪枝有两个：1、如果一个节点连出的边数超了肯定要剪枝。2、利用lim数组，预估在最多的情况下能连几条边，如果少于目标边数，剪枝。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int maxn = 101;
  6 
  7 int n;
  8 int gra[maxn][maxn], lim[maxn][maxn];
  9 int cur[maxn][maxn], ans[maxn][maxn];
 10 int dx[] = { 0,0,1,1 };
 11 int dy[] = { 0,1,0,1 };
 12 
 13 int pre[maxn*maxn];
 14 
 15 int findn(int x) {
 16     return x == pre[x] ? x : findn(pre[x]);
 17 }
 18 
 19 inline bool ok(int x, int y) {
 20     if (gra[x][y] == -1) return true;
 21     if (cur[x][y] <= gra[x][y] && cur[x][y] + lim[x][y] >= gra[x][y]) return true;
 22     return false;
 23 }
 24 
 25 bool dfs(int x, int y) {
 26     if (y == n) x++, y = 1;
 27     if (x == n) return true;
 28 
 29     cur[x][y]++, cur[x + 1][y + 1]++;
 30     lim[x][y]--, lim[x + 1][y]--, lim[x][y + 1]--, lim[x + 1][y + 1]--;
 31     
 32     bool can_put = true;
 33     for (int i = 0; i < 4; i++) {
 34         int xx = x + dx[i], yy = y + dy[i];
 35         if (!ok(xx, yy)) { can_put = false; break; }
 36     }
 37     if (can_put) {
 38         int f1 = findn((x - 1)*n + y), f2 = findn(x*n + y + 1);
 39         if (f1 != f2) {
 40             ans[x][y] = 1;
 41             int tmp = pre[f2];
 42             pre[f2] = f1;
 43             if (dfs(x, y + 1)) return true;
 44             pre[f2] = tmp;
 45         }
 46     }
 47 
 48     cur[x][y]--, cur[x + 1][y + 1]--;
 49     cur[x][y + 1]++, cur[x + 1][y]++;
 50     can_put = true;
 51     for (int i = 0; i < 4; i++) {
 52         int xx = x + dx[i], yy = y + dy[i];
 53         if (!ok(xx, yy)) { can_put = false; break; }
 54     }
 55     if (can_put) {
 56         int f1 = findn(x*n + y), f2 = findn((x - 1)*n + y + 1);
 57         if (f1 != f2) {
 58             ans[x][y] = -1;
 59             int tmp = pre[f1];
 60             pre[f1] = f2;
 61             if (dfs(x, y + 1)) return true;
 62             pre[f1] = tmp;
 63         }
 64     }
 65 
 66     cur[x][y + 1]--, cur[x + 1][y]--;
 67     lim[x][y]++, lim[x + 1][y]++, lim[x][y + 1]++, lim[x + 1][y + 1]++;
 68     return false;
 69 }
 70 
 71 int main()
 72 {
 73     //freopen("input.txt", "r", stdin);
 74     int iCase;
 75     scanf("%d", &iCase);
 76     while (iCase--) {
 77         scanf("%d", &n);
 78         n++;
 79         char ss[maxn];
 80         for (int i = 1; i <= n * n; i++) pre[i] = i;
 81         memset(cur, 0, sizeof(cur));
 82 
 83         for (int i = 1; i <= n; i++) {
 84             scanf("%s", ss + 1);
 85             for (int j = 1; j <= n; j++) {
 86                 if (ss[j] == '.') gra[i][j] = -1;
 87                 else gra[i][j] = ss[j] - '0';
 88 
 89                 lim[i][j] = 4;
 90                 
 91                 if ((i == 1 || i == n) && (j == 1 || j == n)) {
 92                     lim[i][j] = 1;
 93                     continue;
 94                 }
 95                 if (i == 1 || j == 1 || i == n || j == n) {
 96                     lim[i][j] = 2;
 97                 }
 98             }
 99         }
100 
101         dfs(1, 1);
102 
103         for (int i = 1; i < n; i++) {
104             for (int j = 1; j < n; j++) {
105                 if (ans[i][j] == 1) printf("\");
106                 else printf("/");
107             }
108             printf("
");
109         }
110     }
111     return 0;
112 }