1 条题解
-
0
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #define MAXN 41 using namespace std; char maze[MAXN][MAXN]; int T; int w, h; int sx, sy, ex, ey; int dirx[] = { 0, -1, 0, 1 }; int diry[] = { -1, 0, 1, 0 }; //L,U,R,D struct Location{ int x, y, step; Location(){} Location(int xx, int yy, int ss) :x(xx), y(yy), step(ss){} }; void DFS(int x, int y, int& step, int face, int rule) { for (int i = 0; i < 4; i++) { int index, xx, yy; if (rule == 1)//left index = (face + 3 + i) % 4; else//right index = (face + 5 - i) % 4; xx = x + dirx[index]; yy = y + diry[index]; if (xx == ex && yy == ey) { step++; break; } else if (xx < 0 || xx >= h || yy < 0 || yy >= w) continue; else if (maze[xx][yy] == '#') continue; else { DFS(xx, yy, ++step, index, rule); break; } } } int BFS() { bool vis[MAXN][MAXN]; memset(vis, 0, sizeof(vis)); vis[sx][sy] = true; queue<Location> q; q.push(Location(sx, sy, 1)); while (!q.empty()) { Location p = q.front(); q.pop(); if (p.x == ex && p.y == ey) return p.step; for (int i = 0; i < 4; i++) { Location tmp(p.x + dirx[i], p.y + diry[i], p.step + 1); if (tmp.x < 0 || tmp.x >= h || tmp.y < 0 || tmp.y >= w) continue; if (maze[tmp.x][tmp.y] != '#'&&!vis[tmp.x][tmp.y]) { q.push(tmp); vis[tmp.x][tmp.y] = true; } } } } int main(int argc, char** argv) { scanf("%d", &T); while (T--) { scanf("%d%d", &w, &h); for (int i = 0; i < h; i++) { scanf("%s", maze[i]); for (int j = 0; j < w; j++) { //scanf(" %c", &maze[i][j]); if (maze[i][j] == 'S') { sx = i; sy = j; } else if (maze[i][j] == 'E') { ex = i; ey = j; } } } int face; if (sx == 0) face = 3; else if (sx == h - 1) face = 1; else if (sy == 0) face = 2; else face = 0; int step = 1; DFS(sx, sy, step, face, 1); printf("%d ", step); step = 1; DFS(sx, sy, step, face, 0); printf("%d ", step); printf("%d\n", BFS()); } return 0; }
- 1
信息
- ID
- 2084
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者