今天说一道题吧!
题意:
看洛谷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] = '