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; }
-
0
#include<bits/stdc++.h> using namespace std; const int N=1e2+10; char maze[N][N]; int vis[N][N]; int dirx[]={0,0,-1,1}; int diry[]={-1,1,0,0}; int n,m; struct node1{ int x,y,w; }; queueque; bool check(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]0&&maze[x][y]'.') return true; return false; } int bfs() { que.push({0,0,1}); while(!que.empty()) { node1 p=que.front(); que.pop(); if(p.xn-1&&p.ym-1) return p.w ; if(vis[p.x][p.y]) continue; vis[p.x][p.y]=true; for(int i=0;i<4;i++) { int nx=dirx[i]+p.x; int ny=diry[i]+p.y; if(check(nx,ny)) que.push({nx,ny,p.w+1}); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>maze[i][j]; cout<<bfs()<<endl; return 0; }
-
0
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> #include <string.h> #include <queue> #include <stack> #include <map> #include <set> #include <vector> using namespace std; int n,m; char a[45][45]; int vis[45][45]; struct temp { int tx; int ty; int step; }; int nx[4]= {0,0,1,-1}; int ny[4]= {1,-1,0,0}; queue<temp> q; void bfs() { while(!q.empty()) { temp t=q.front(); q.pop(); if(t.tx==n-1&&t.ty==m-1) { cout<<t.step; return; } if(vis[t.tx][t.ty]) continue; vis[t.tx][t.ty]=1; for(int i=0; i<4; i++) { int x=t.tx+nx[i],y=t.ty+ny[i]; if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==0&&a[x][y]=='.') q.push({x,y,t.step+1}); } } } int main() { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { cin>>a[i]; } q.push({0,0,1}); bfs(); return 0; }
- 1
Information
- ID
- 769
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 7
- Tags
- # Submissions
- 444
- Accepted
- 87
- Uploaded By