POJ3083-Children of the Candy Corn
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<queue> #define MAXNUM 10020 using namespace std; int n, m; bool mp[50][50], mark[50][50]; bool flag; char tmp[60]; int LPath, RPath, SPath, Path; int Dir[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; struct Point { int x, y; }start, en; void LDFS(int x, int y, int dir) { if (x == en.x && y == en.y) return; int a, b, i, j; for (i = dir - 1; i < dir + 3; i++) { j = (i + 4) % 4; a = x + Dir[j][0]; b = y + Dir[j][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b]) break; } } LPath++; LDFS(a, b, j); } void RDFS(int x, int y, int dir) { if (x == en.x && y == en.y) return; int a, b, i, j; for (i = dir + 1; i > dir - 3; i--) { j = (4 + i) % 4; a = x + Dir[j][0]; b = y + Dir[j][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b]) { break; } } } RPath++; RDFS(a, b, j); } void SDFS(int x, int y, int dir) { queue<Point> record; int i, j, k, t, a, b; Point tmp; tmp.x = x; tmp.y = y; record.push(tmp); SPath = 0; flag = 0; while (true) { t = record.size(); SPath++; while (t > 0) { i = record.front().x; j = record.front().y; record.pop(); if (i == en.x&&j == en.y) { flag = 1; break; } for (k = 0; k < 4; k++) { a = i + Dir[k][0]; b = j + Dir[k][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b] && !mark[a][b]) { mark[a][b] = 1; Point tmp; tmp.x = a; tmp.y = b; record.push(tmp); } } } t--; } if (flag) break; } } int main() { freopen("1.txt", "r", stdin); int i, j, k, t, a, b, cases, dir; bool flag; scanf("%d", &cases); while (cases > 0) { scanf("%d%d", &n, &m); memset(mp, 0, sizeof(mp)); for (i = 0; i < m; i++) { scanf("%s", tmp); for (j = 0; j < n; j++) { if (tmp[j] == '.') mp[i][j] = 1; else if (tmp[j] == 'S') { mp[i][j] = 1; start.x = i; start.y = j; if (i == 0) dir = 2; else if (i == (m - 1)) dir = 0; else if (j == 0) dir = 1; else if (j == (n - 1)) dir = 3; } else if (tmp[j] == 'E') { mp[i][j] = 1; en.x = i; en.y = j; } } } LPath = RPath = 0; LDFS(start.x, start.y, dir); RDFS(start.x, start.y, dir); memset(mark, 0, sizeof(mark)); SDFS(start.x, start.y, dir); printf("%d %d %d\n",LPath+1, RPath + 1, SPath); cases--; } return 0; }不知道为什么原来的代码是错的：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<queue> #define MAXNUM 10020 using namespace std; int n, m; bool mp[50][50], mark[50][50], flag; char tmp[60]; int LPath, RPath, SPath, Path; int Dir[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; struct Point { int x, y; }start, en; void LDFS(int x,int y,int dir) { if (flag) return; if (x == en.x && y == en.y) { flag = 1; return; } int a, b, i, j; for (i = dir-1; i < dir + 3; i++) { j = (i + 4) % 4; a = x + Dir[j][0]; b = y + Dir[j][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b]) { LPath++; LDFS(a, b, j); if (flag) return; } } } } void RDFS(int x, int y, int dir) { if (flag) return; if (x == en.x && y == en.y) { flag = 1; return; } int a, b, i, j; for (i = dir + 1; i > dir - 3; i--) { j = (4 + i) % 4; a = x + Dir[j][0]; b = y + Dir[j][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b]) { RPath++; RDFS(a, b, j); if (flag) return; } } } } void SDFS(int x, int y, int dir) { queue<Point> record; int i, j, k, t, a, b; Point tmp; tmp.x = x; tmp.y = y; record.push(tmp); SPath = 0; flag = 0; while (true) { t = record.size(); SPath++; while (t > 0) { i = record.front().x; j = record.front().y; record.pop(); if (i == en.x&&j == en.y) { flag = 1; break; } for (k = 0; k < 4; k++) { a = i + Dir[k][0]; b = j + Dir[k][1]; if (a >= 0 && a < m&&b >= 0 && b < n) { if (mp[a][b] && !mark[a][b]) { mark[a][b] = 1; Point tmp; tmp.x = a; tmp.y = b; record.push(tmp); } } } t--; } if (flag) break; } } int main() { freopen("1.txt", "r", stdin); int i, j, k, t, a, b, cases, dir; bool flag; scanf("%d", &cases); while (cases > 0) { scanf("%d%d", &n, &m); memset(mp, 0, sizeof(mp)); for (i = 0; i < m; i++) { scanf("%s", tmp); for (j = 0; j < n; j++) { if (tmp[j] == '.') mp[i][j] = 1; else if (tmp[j] == 'S') { mp[i][j] = 1; start.x = i; start.y = j; if (i == 0) dir = 2; else if (i == (m - 1)) dir = 0; else if (j == 0) dir = 1; else if (j == (n - 1)) dir = 3; } else if (tmp[j] == 'E') { mp[i][j] = 1; en.x = i; en.y = j; } } } LPath = RPath = 0; flag = 0; //LDFS(start.x, start.y, dir); //flag = 0; RDFS(start.x, start.y, dir); memset(mark, 0, sizeof(mark)); SDFS(start.x, start.y, dir); printf("%d %d\n", RPath+1, SPath); cases--; } return 0; }