3 solutions
-
1
#include<iostream> #include<queue> using namespace std; struct Point { int x; //用结构体表示此时坐标和已走步数 int y; int step; }; void bfs(); int R, C; char mp[105][105]; bool vis[105][105] = {}; queue<Point> q; int main() { cin >> R >> C; for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) cin >> mp[i][j]; q.push({ 1,1,1 }); bfs(); return 0; } void bfs() { int x, y; Point p; int dx[4] = {0,0,1,-1}; int dy [4] = {1,-1,0,0}; while(!q.empty()) { p = q.front(); q.pop(); if (p.x == C && p.y == R) { cout << p.step; return; } if (vis[p.x][p.y]) continue; vis[p.x][p.y] = true; for (int i = 0; i < 4; i++) { x = p.x + dx[i]; y = p.y + dy[i]; if (x > 0 && x <= C && y > 0 && y <= R && vis[x][y] == false && mp[x][y] == '.') q.push({ x,y,p.step + 1 }); } } cout << -1 << endl; }
Information
- ID
- 769
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 7
- Tags
- # Submissions
- 445
- Accepted
- 88
- Uploaded By