基本思路是Dfs：
1. 一个一个格子摆放，以每个各自的左上角的点为基准点代表格子，比如（0，0）代表（0，0）（0，1）（1，0）（1，1）组成的格子，（0，1）代表（0，1）（0，2）（1，1），（1，2）组成的格子，以此类推，即可一个一个格子按顺序摆放。
2. 当摆放（x，y）时，比较分别放 \ 和放 / ，同时比较（x，y）的数值要求是否已经达到（不能多不能少，（x，y）必须刚好达到），其次比较另外的如（x+1，y），（x+1,y+1），（x,
y+1）是否已经超出要求。再者就是判断是否构成环，我采用了dfs的方法。
3. 如何表示这个点连接几条斜线了呢？可以用一个数组保存，如point[i][j] 表示(i, j)连接了point[i][j]条斜线。而判断两个点是否连接可以用link[][][][]，如link[a][b][c][d]，表示link[a][b][c][d]是否连接。
一点收获与感悟：最初写的时候，没有link数组，想用point[a][b]和point[c][d]是否同时大于1判断(a, b)与(c,d)是否连接，结果可想而知，这个错误明显了！发现这个错误后才加入了link数组。但这样只是解决了错误，还没有解决超时。刚开始写的时候只判断了（x，y）是否满足要求，没有判断其它点，后来一想，可能再给（x, y）（x+1, y+1）相连时，（x+1, y+1）连接的边数就超过（x+1, y+1）要求的边数了，所以要同时判断与（x，y）相连的点，这个判断一添，就没有超时了。
#include <bits/stdc++.h> using namespace std; const int MAXN = 7 + 3;
char chess[MAXN][MAXN];
int point[MAXN][MAXN];
bool link[MAXN][MAXN][MAXN][MAXN];
int N;
int go[4][2] = {1,1, 1,-1, -1,-1, -1,1}; void Read() {
for(int i=0; i<N+1; ++ i) {
for(int j=0; j<N+1; ++ j) {
cin >> chess[i][j];
}
}
} bool vis[MAXN][MAXN];
bool found; void Loop(int x, int y, int a, int b) {
if(found || x<0 || x>N || y<0 || y>N || !link[x][y][a][b] ) {
return ;
}
if(vis[x][y]) {
found = true;
return ;
}
vis[x][y] = true;
for(int i=0; i<4; ++i) {
if( x+go[i][0]!=a || y+go[i][1]!=b ) {
Loop(x+go[i][0], y+go[i][1], x, y);
}
}
} bool Any(int x, int y) {
memset(vis, false, sizeof(vis));
found = false;
vis[x][y] = true;
Loop(x+1, y+1, x, y);
Loop(x-1, y-1, x, y);
Loop(x-1, y+1, x, y);
Loop(x+1, y-1, x, y);
return !found;
} bool Dfs(int r, int c) {
if(c == N) {
if( isdigit(chess[r][c]) && point[r][c] != chess[r][c] - '0') {
return false;
}
++ r; c = 0;
if(r == N) {
for(int i=0; i<N+1;i++) {
if(isdigit(chess[r][i]) && point[r][i] != chess[r][i] - '0') {
return false;
}
}
return true;
} else {
return Dfs(r, c);
}
}
int x = r, y = c;
point[x][y] ++;
point[x+1][y+1] ++;
link[x][y][x+1][y+1] = true;
link[x+1][y+1][x][y] = true;
if( isdigit(chess[x][y]) && point[x][y] != chess[x][y] - '0') {
;
} else if(isdigit(chess[x+1][y+1]) && point[x+1][y+1] > chess[x+1][y+1] - '0') {
;
} else if(Any(x, y)) {
++ y;
if(Dfs(x, y)) {
return true;
}
}
x = r, y =c;
link[x][y][x+1][y+1] = false;
link[x+1][y+1][x][y] = false;
point[x][y] --;
point[x+1][y+1] --; point[x][y+1] ++;
point[x+1][y] ++;
link[x][y+1][x+1][y] = true;
link[x+1][y][x][y+1] = true;
if( isdigit(chess[x][y]) && point[x][y] != chess[x][y] - '0') {
;
} else if(isdigit(chess[x][y+1]) && point[x][y+1] > chess[x][y+1] - '0') {
;
} else if(isdigit(chess[x+1][y]) && point[x+1][y] > chess[x+1][y] - '0') {
;
} else if(Any(x, y+1)) {
++ y;
if(Dfs(x, y)) {
return true;
}
}
x = r, y =c;
link[x][y+1][x+1][y] = false;
link[x+1][y][x][y+1] = false;
point[x][y+1] --;
point[x+1][y] --;
return false;
} void Work() {
memset(point, 0, sizeof(point));
memset(link, false, sizeof(link));
Dfs(0 ,0);
} void Print() {
for(int i=0; i<N; ++i) {
for(int j=0; j<N; ++j) {
if(point[i][j] && point[i+1][j+1] && link[i][j][i+1][j+1]) {
cout << "\\";
} else {
cout << "/";
}
}
cout << endl;
}
} int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T --) {
cin >> N;
Read();
Work();
Print();
}
return 0;
}