---恢復(fù)內(nèi)容開始---

這道題的題解很多，所以就不用說明了。

下面便是單dfs與雙dfs的代碼?

?900ms

// UVa 1601 // bfs（原始） #include <cstdio> #include <cstring> #include <cctype> #include <queue> using namespace std; const int maxc = 20; const int maxn = 256; const int dx[] = {-1, 1, 0, 0, 0}; const int dy[] = {0, 0, -1, 1, 0};int w, h, n; int s[3], t[3]; int deg[maxn], G[maxn][5]; int get_ID(int a, int b, int c) {return (a<<16)|(b<<8)|c; }bool is_conflict(int a, int b, int a1, int b1) {return (a1 == b1) || (a == b1 && b == a1); }int dist[maxn][maxn][maxn]; int bfs() {queue<int> q;memset(dist, -1, sizeof(dist)); q.push(get_ID(s[0], s[1], s[2])); dist[s[0]][s[1]][s[2]] = 0;while (!q.empty()) {int u = q.front(); q.pop();int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff; if (a == t[0] && b == t[1] && c == t[2]) return dist[a][b][c]; for (int i = 0; i < deg[a]; ++i) {int a1 = G[a][i]; for (int j = 0; j < deg[b]; ++j) {int b1 = G[b][j]; if (is_conflict(a, b, a1, b1)) continue; for (int k = 0; k < deg[c]; ++k) {int c1 = G[c][k];if (is_conflict(a, c, a1, c1)) continue; if (is_conflict(b, c, b1, c1)) continue; if (dist[a1][b1][c1] != -1) continue; dist[a1][b1][c1] = dist[a][b][c] + 1;q.push(get_ID(a1, b1, c1)); }} }}return -1; }int main() {while (scanf("%d%d%d\n", &w, &h, &n) == 3 && n) {int cnt = 0, x[maxn], y[maxn], id[maxc][maxc];char input[maxc][maxc]; for (int i = 0; i < h; ++i)fgets(input[i], maxc, stdin); for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) if (input[i][j] != '#') {x[cnt] = i; y[cnt] = j; id[i][j] = cnt; if (islower(input[i][j])) s[input[i][j]-'a'] = cnt; else if (isupper(input[i][j])) t[input[i][j]-'A'] = cnt; cnt++; }for (int i = 0; i < cnt; ++i) {deg[i] = 0;for (int j = 0; j < 5; ++j) {int x1 = x[i]+dx[j], y1 = y[i]+dy[j];if (input[x1][y1] != '#') G[i][deg[i]++] = id[x1][y1];}}if (n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; }if (n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; } printf("%d\n", bfs()); }return 0; }

750ms

// UVa 1601 // 雙向bfs #include <cstdio> #include <cstring> #include <cctype> #include <queue> using namespace std; const int maxc = 20; const int maxn = 256; const int dx[] = {1, -1, 0, 0, 0}; const int dy[] = {0, 0, 1, -1, 0}; int w, h, n; int deg[maxn], G[maxn][5]; int s[3], t[3]; int ID(int a, int b, int c) { return (a<<16)|(b<<8)|c; }bool is_conflict(int a, int b, int a1, int b1) {return (a1 == b1) || (a == b1 && b == a1); }int ds[maxn][maxn][maxn]; int dt[maxn][maxn][maxn]; int dfs() {queue<int> qs, qt; qs.push(ID(s[0], s[1], s[2])); qt.push(ID(t[0], t[1], t[2])); memset(ds, -1, sizeof(ds));memset(dt, -1, sizeof(dt));ds[s[0]][s[1]][s[2]] = dt[t[0]][t[1]][t[2]] = 0;while (!qs.empty() && !qt.empty()) {{int u = qs.front(); qs.pop(); int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;for (int i = 0; i < deg[a]; ++i) {int a1 = G[a][i]; for (int j = 0; j < deg[b]; ++j) {int b1 = G[b][j]; if (is_conflict(a, b, a1, b1)) continue; for (int k = 0; k < deg[c]; ++k) {int c1 = G[c][k];if (is_conflict(a, c, a1, c1)) continue; if (is_conflict(b, c, b1, c1)) continue;if (ds[a1][b1][c1] == -1) { ds[a1][b1][c1] = ds[a][b][c] + 1; qs.push(ID(a1, b1, c1)); } if (dt[a1][b1][c1] != -1) return ds[a1][b1][c1] + dt[a1][b1][c1]; }}}}{int u = qt.front(); qt.pop(); int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;for (int i = 0; i < deg[a]; ++i) {int a1 = G[a][i]; for (int j = 0; j < deg[b]; ++j) {int b1 = G[b][j]; if (is_conflict(a, b, a1, b1)) continue; for (int k = 0; k < deg[c]; ++k) {int c1 = G[c][k];if (is_conflict(a, c, a1, c1)) continue; if (is_conflict(b, c, b1, c1)) continue;if (dt[a1][b1][c1] == -1) { dt[a1][b1][c1] = dt[a][b][c] + 1; qt.push(ID(a1, b1, c1)); }if (ds[a1][b1][c1] != -1) return dt[a1][b1][c1] + ds[a1][b1][c1]; }}}}}return -1; } int main() { while (scanf("%d%d%d\n", &w, &h, &n) == 3 && n) { char input[maxc][maxc]; int cnt = 0, x[maxn], y[maxn], id[maxc][maxc]; for (int i = 0; i < h; ++i) fgets(input[i], maxc, stdin); for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) if (input[i][j] != '#') {x[cnt] = i; y[cnt] = j; id[i][j] = cnt; if (islower(input[i][j])) s[input[i][j]-'a'] = cnt; else if (isupper(input[i][j])) t[input[i][j]-'A'] = cnt; cnt++; }for (int i = 0; i < cnt; ++i) {deg[i] = 0; for (int j = 0; j < 5; ++j) {int x1 = x[i]+dx[j], y1 = y[i]+dy[j];if (input[x1][y1] != '#') { G[i][deg[i]++] = id[x1][y1]; } }}if (n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; } if (n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; }printf("%d\n", dfs()); }return 0; }

單dfs的查詢節(jié)點大概是 n ^ len

雙dfs的查詢節(jié)點大概是 2 * n ^ (len / 2)?

n, len越大優(yōu)化程度越高

轉(zhuǎn)載于:https://www.cnblogs.com/yifeiWa/p/11019233.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的UVa1601的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。