題意：在一個n*n（n7）網格中，有些交叉點上有數字。你的任務是給每個格子畫一條斜線（“/”和“\”），使得每個交叉點的數字等于和他們相連的斜線條數，且這些斜線不會構成環。

分析：方法是dfs，交叉點數字解決方法是以放入“\”和“/”為搜索對象，方格的端的有數字就減一，沒數字就剪枝，其中有很多剪枝，比如每當搜索完一個方格后，方格的左端點如果是數字，那么數字應該為0，依次類推，方格處于右端，左上應該為0等等。其中關鍵難點是判斷是否有環。看一位大佬的解法，以最新放進去的方格內容為對象，搜索方格四周，當點重復被搜索時，說明存在環。

bool loop(int r, int c, int f) { //判斷是否有環if (vis[r][c] == mark) return true;vis[r][c] = mark; //每次都給他賦值，這個mark沒有實際意義，只是避免和上次搜索重復for (int i = 0; i < 4; i++) {if ((i ^ 1) == f) continue; //i的相反方向是否等于fint fr = r + dr[i], fc = c + dc[i]; //搜索四周if (edge[r][c][fr][fc] == 0) continue; //判斷是否有邊if (loop(fr, fc, i)) return true;}return false; }

寫的很簡單，但非常實用！

#include <cstdio> #include <cstring> #include <cctype>const int UP = 7 + 5; const int dr[4] = { -1, 1, -1, 1 }; //左上，右下，右上，左下 const int dc[4] = { -1, 1, 1, -1 }; const int udr[2] = { 0, 0 }; //反斜杠和斜杠的上方坐標 const int udc[2] = { 0, 1 }; const int ddr[2] = { 1, 1 }; //反斜杠和斜杠的下方坐標 const int ddc[2] = { 1, 0 };int n, N, finish, mark, vis[UP][UP]; char grid[UP][UP], ans[UP][UP], edge[UP][UP][UP][UP]; //ans[r][c] 與 grid[r][c], grid[r][c+1], grid[r+1][c], grid[r+1][c+1] 相關聯 //r與c的下標從1開始void renew(int r1, int c1, int r2, int c2) { //恢復狀態if (isdigit(grid[r1][c1])) grid[r1][c1]++;if (isdigit(grid[r2][c2])) grid[r2][c2]++; }bool loop(int r, int c, int f) { //判斷是否有環if (vis[r][c] == mark) return true;vis[r][c] = mark; //每次都給他賦值，這個mark沒有實際意義，只是避免和上次搜索重復for (int i = 0; i < 4; i++) {if ((i ^ 1) == f) continue; //i的相反方向是否等于fint fr = r + dr[i], fc = c + dc[i]; //搜索四周if (edge[r][c][fr][fc] == 0) continue; //判斷是否有邊if (loop(fr, fc, i)) return true;}return false; }bool dfs(int id) {if (id == finish) return true;if (id % N == 0) return dfs(id + 1); //該位置不做考慮，只是下一個位置的過渡int r = id / N, c = id % N;int jr = r + udr[0], jc = c + udc[0]; //判斷該位置的數字是否大于0所用for (int i = 0; i < 2; i++) {int ufr = r + udr[i], ufc = c + udc[i];int dfr = r + ddr[i], dfc = c + ddc[i];if (isdigit(grid[ufr][ufc]) && grid[ufr][ufc] - 1 < '0') continue;if (isdigit(grid[dfr][dfc]) && grid[dfr][dfc] - 1 < '0') continue;if (isdigit(grid[ufr][ufc])) grid[ufr][ufc]--;if (isdigit(grid[dfr][dfc])) grid[dfr][dfc]--;if (grid[jr][jc] > '0') { //剪枝1renew(ufr, ufc, dfr, dfc);continue;}if (r == n) { //剪枝2int sr = r + ddr[1], sc = c + ddc[1];if (grid[sr][sc] > '0') {renew(ufr, ufc, dfr, dfc);continue;}}if (c == n) { //剪枝3int sr = r + udr[1], sc = c + udc[1];if (grid[sr][sc] > '0') {renew(ufr, ufc, dfr, dfc);continue;}}if (r == n && c == n) { //剪枝4int sr = r + ddr[0], sc = c + ddc[0];if (grid[sr][sc] > '0') {renew(ufr, ufc, dfr, dfc);continue;}}ans[r][c] = i;edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 1;mark++;if (loop(dfr, dfc, -1)) {edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 0;renew(ufr, ufc, dfr, dfc);continue;}if (dfs(id + 1)) return true;edge[ufr][ufc][dfr][dfc] = edge[dfr][dfc][ufr][ufc] = 0;renew(ufr, ufc, dfr, dfc);}return false; }int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &n);N = n + 1;for (int r = 1; r <= N; r++) scanf("%s", grid[r] + 1);memset(vis, 0, sizeof(vis));memset(edge, 0, sizeof(edge));mark = 1;finish = N * N;dfs(N + 1);for (int r = 1; r <= n; r++) {for (int c = 1; c <= n; c++) {if (ans[r][c] == 0) printf("\\");else printf("/");}printf("\n");}}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 11694 Gokigen Naname（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。