首页 > 代码库 > UVa11882 Biggest Number (DFS+剪枝)
UVa11882 Biggest Number (DFS+剪枝)
链接：http://vjudge.net/problem/23314
分析：两种剪枝方案。
1.找出在当前位置下还能够到达的点的个数（尽管实际能到达的点的个数比它小，但乐观估计就可以了），若当前数字加上个数仍小于目前最优解的长度，则剪枝。
2.若将还能够到达的数字按从小到大连接到当前数字后面，若仍比目前最优解小，则剪枝。（找出所有还能够到达的点用BFS实现（乐观估计））。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <cstring> 6 #include <queue> 7 using namespace std; 8 9 const int maxn = 15 + 5;10 11 int n, m, v[30];12 string ans;13 char maze[maxn][maxn];14 bool vis[maxn][maxn], mark[maxn][maxn];15 16 bool smaller(string num) {17 if (num.size() > ans.size()) return true;18 else if (num.size() == ans.size() && num > ans) return true;19 else return false;20 }21 22 const int dx[4] = {1, -1, 0, 0};23 const int dy[4] = {0, 0, 1, -1};24 int bfs(int x, int y) {25 queue<pair<int, int> > q;26 memset(mark, 0, sizeof(mark));27 q.push(make_pair(x, y));28 mark[x][y] = true;29 int cnt = 0;30 while (!q.empty()) {31 pair<int, int> u = q.front(); q.pop();32 for (int dir = 0; dir < 4; dir++) {33 int nx = u.first + dx[dir], ny = u.second + dy[dir];34 if (nx < 1 || nx > n || ny < 1 || ny > m) continue;35 if (maze[nx][ny] == ‘#‘ || vis[nx][ny] || mark[nx][ny]) continue;36 mark[nx][ny] = true;37 v[cnt++] = maze[nx][ny] - ‘0‘;38 q.push(make_pair(nx, ny));39 }40 }41 return cnt;42 }43 44 void dfs(int x, int y, string num) {45 if (smaller(num)) ans = num;46 else {47 int cnt = bfs(x, y);48 if (num.size() + cnt < ans.size()) return;49 if (num.size() + cnt == ans.size()) {50 sort(v, v + cnt);51 string num2 = num;52 for (int i = cnt - 1; i >= 0; i--)53 num2 += char(v[i] + ‘0‘);54 if (!smaller(num2)) return;55 }56 }57 for (int dir = 0; dir < 4; dir++) {58 int nx = x + dx[dir], ny = y + dy[dir];59 if (nx < 1 || nx > n || ny < 1 || ny > m) continue;60 if (maze[nx][ny] == ‘#‘) continue;61 if (vis[nx][ny]) continue; else vis[nx][ny] = true;62 dfs(nx, ny, num + maze[nx][ny]);63 vis[nx][ny] = false;64 }65 }66 67 void solve() {68 for (int i = 1; i <= n; i++)69 for (int j = 1; j <= m; j++) {70 if (maze[i][j] == ‘#‘) continue;71 memset(vis, false, sizeof(vis));72 vis[i][j] = true;73 string num = "";74 num += maze[i][j];75 dfs(i, j, num);76 }77 cout << ans << endl;78 }79 80 int main() {81 while (cin >> n >> m && n) {82 for (int i = 1; i <= n; i++) scanf("%s", maze[i] + 1);83 ans.clear(); solve();84 }85 return 0;86 }
UVa11882 Biggest Number (DFS+剪枝)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。