hihoCoder 1519-逃离迷宫II

---

给定一个迷宫，S表示起点，T表示终点，#表示障碍物。行走的时候，只能沿着直线走，直到遇到障碍物或者碰壁，问从S到T，最少需要改变多少次方向。 我一开始是用DFS做的，每次朝一个方向DFS下去，但是因为每次DFS时走了一长条直线，所以回溯的时候需要把之前走过的直线复位。代码如下： [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> using namespace std; const int MAXN = 505; int n, m; int startx, starty, endx, endy; int ans = INT_MAX; vector<vector<char>> maze(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<char>> visited(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向 bool ok(int x, int y) { if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != ‘#’)return true; return false; } void dfs(int sx,int sy, int step) { for (int i = 0; i < 4; ++i) { int newx = sx + dirs[i][0], newy = sy + dirs[i][1]; if (ok(newx, newy) && visited[newx][newy] == ‘0’) { visited[newx][newy] = ‘1’; bool done = false; while (ok(newx, newy)) { visited[newx][newy] = ‘1’; if (newx == endx&&newy == endy) { done = true; break; } newx = newx + dirs[i][0], newy = newy + dirs[i][1]; } if (done) { ans = min(ans, step); } else { dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1); // 往回走一步再递归 } while (!(newx == sx&&newy == sy)) { if (ok(newx, newy))visited[newx][newy] = ‘0’; // 复位 newx = newx + opdirs[i][0], newy = newy + opdirs[i][1]; } } } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); for (int j = 0; j < m; ++j) { scanf("%c", &maze[i][j]); if (maze[i][j] == ‘S’) { startx = i; starty = j; } else if (maze[i][j] == ‘T’) { endx = i; endy = j; } } } visited[startx][starty] = ‘1’; dfs(startx, starty, 0); if (ans == INT_MAX)printf("-1\n"); else printf("%d\n", ans); return 0; } [/cpp] 本代码提交TLE，很明显会TLE，因为DFS必须把所有方案都走一遍才能得到最小值。 比赛的时候脑子短路，这种搜索问题要求最短XX的肯定用BFS比DFS快呀，因为第一次BFS到的方案肯定就是最优方案呀。只不过这题判断距离用的是转弯次数，以前都是算走过的步数。 对于这题，用BFS也是一样的，BFS的下一个点肯定就是走直线走到无法再走的那个拐角点（cornor）。不过为了防止死循环，要把以前走过的拐角都记录下来，只走那些以前没走过的拐点。 代码如下： [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> #include<queue> using namespace std; const int MAXN = 505; int n, m; int startx, starty, endx, endy; typedef struct P { int x, y, step; P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {}; }; vector<vector<char>> maze(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向 set<int> points; bool ok(int x, int y) { if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != ‘#’)return true; return false; } int id(int x, int y) { return x*n + y; } int bfs() { queue<P> q; P p(startx, starty, 0); q.push(p); while (!q.empty()) { p = q.front(); q.pop(); points.insert(id(p.x, p.y)); for (int i = 0; i < dirs.size(); ++i) { int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1]; while (ok(newx, newy)) { if (newx == endx&&newy == endy) { return p.step; } newx = newx + dirs[i][0], newy = newy + dirs[i][1]; } int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步 if (points.find(id(cornorx, cornory)) == points.end()) { P tmp(cornorx, cornory, p.step + 1); q.push(tmp); } } } return -1; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); for (int j = 0; j < m; ++j) { scanf("%c", &maze[i][j]); if (maze[i][j] == ‘S’) { startx = i; starty = j; } else if (maze[i][j] == ‘T’) { endx = i; endy = j; } } } printf("%d\n", bfs()); return 0; } [/cpp] 本代码提交AC，用时718MS。]]>