| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
模拟+bfs(贴左右墙走的代码可以合并~)#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> using namespace std; const int N = 40 + 5; int size_x, size_y; int st_x, st_y, end_x, end_y; char map[N][N]; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { -1, 0, 1, 0 }; int queue[N * N], step[N][N]; bool pd[N][N]; #define rotate(p,dir) ((p + dir + 4) % 4) int go(int dir) // -1-left, 1-right { int p, cnt = 0; if (st_x - 1 >= 0 && st_x - 1 < size_x && map[st_x - 1][st_y] == '#') p = (st_y == 0 ? 2 : 0); else p = (st_x == 0 ? 1 : 3); int x = st_x, y = st_y; while (x != end_x || y != end_y) { while (map[y + dy[p]][x + dx[p]] == '#') p = rotate(p, -dir); x += dx[p]; y += dy[p]; cnt++; if (map[y + dy[rotate(p, dir)]][x + dx[rotate(p, dir)]] != '#') p = rotate(p, dir); } return cnt + 1; } #define ok(x,y) (x >= 0 && x < size_x && y >= 0 && y < size_y) int bfs() { int l = 0, r = 0; memset(pd, false, sizeof(pd)); step[st_x][st_y] = 1; queue[r++] = st_x * size_x + st_y; while (l < r) { int p = queue[l++]; for (int i = 0; i < 4; i++) { int x = p / size_x, y = p % size_x; int x1 = x + dx[i], y1 = y + dy[i]; if (!pd[x1][y1] && ok(x1, y1) && map[y1][x1] != '#') { queue[r++] = x1 * size_x + y1; pd[x1][y1] = true; step[x1][y1] = step[x][y] + 1; if (x1 == end_x && y1 == end_y) return step[x1][y1]; } } } return -1; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d\n", &size_x, &size_y); for (int i = 0; i < size_y; i++) { gets(map[i]); for (int j = 0; j < size_x; j++) if (map[i][j] == 'S') st_x = j, st_y = i; else if (map[i][j] == 'E') end_x = j, end_y = i; } printf("%d %d %d\n", go(-1), go(1), bfs()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator