今天说一道题吧！
题意：
看洛谷https://www.luogu.org/problemnew/show/UVA11882
思路：
根据这道题R,C不是特别大我们可以考虑使用搜索的方法去做，那么根据R*C=30我们知道普通的dfs会超时，
所以必须考虑剪枝。
怎么剪枝？如果我们只看数字的大小是不科学的（例如99与10000），只看位数也不行，
所以比较的时候我们既需要看位数同时需要看大小，这可怎么办啊？
当时我就困在这一点了，我发现同时追求这两个是无法剪枝的。
那么就剪不了了吗？
当然不会，既然同时满足不了，那么我们在位数相同时比较数字可以吗？可以的。
那位数又怎么办呢？
我们可以采用枚举位数，然后根据位数来确定数字。
将一个问题分开去想，能够剪枝并且解决问题。
于是我们说一说实现（代码）
我们首先类似迭代加深搜索来确定位数，然后在位数确定的时候填数。
如果能够满足这个位数，那么后面我们就不在去枚举比较小的位数了（位数从大到小枚举）（剪枝1）
如果我们得到了当前的最优解，那么对于某个时刻来说，我们需要判断已经确定的部分是否能够大于或者等于最优解。（剪枝2）
这样我们就不会超时了，下面是代码
// UVa 11882 // 迭代加深 + 剪枝 // 剪枝策略：将之前最优解记录下来，判断当前来讲是否优于最优解 #include <cstdio> #include <cstring> using namespace std; const int maxn = 20; char square[maxn][maxn], ans[50], num[50]; int R, C, vis[maxn][maxn], maxd, ok; bool cmp(int depth) { if (strlen(ans) == 0) return true; for (int i = 0; i < depth; ++i) if (num[i] != ans[i]) return num[i] > ans[i]; return true; } const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; void dfs(int curx, int cury, int depth) { if (depth == maxd) { ok = 1; num[depth] = ‘\0‘; if (cmp(depth)) memcpy(ans, num, sizeof(num)); return; } for (int i = 0; i < 4; ++i) { int x = curx+dx[i], y = cury+dy[i]; if (x >= 0 && x < R && y >= 0 && y < C) { if (vis[x][y] == 1 && square[x][y] != ‘#‘) { vis[x][y] = 0; num[depth] = square[x][y]; if (cmp(depth)) dfs(x, y, depth+1); vis[x][y] = 1; } } } return; } void init() { for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) vis[i][j] = 1; } int main() { while (scanf("%d%d", &R, &C) == 2 && R) { int cnt = 0; for (int i = 0; i < R; ++i) { scanf("%s", square[i]); for (int j = 0; j < C; ++j) if (square[i][j] != ‘#‘) ++cnt; } ok = 0; memset(ans, 0, sizeof(ans)); init(); for (maxd=cnt; ; --maxd) { for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) if (square[i][j] != ‘#‘) { num[0] = square[i][j]; vis[i][j] = 0; dfs(i, j, 1); init(); } if (ok) break; } printf("%s\n", ans); } return 0; }
不会的留言或者加我qq，我会耐心回答的。
原文：https://www.cnblogs.com/yifeiWa/p/11157949.html