题目一
解题思路
比较标准的暴力搜索+空间换时间的策略
二维数组map表示具体地图,far表示遍历过程中某点到起点的距离。
队列 q 表示在遍历过程中当前距离的所以节点坐标。
每次的节点寻找其上下左右四个方向可以继续前进的点(这里在过程中会发生两个点循环的情况,不过不影响结果,有兴趣可以优化一下)。
边界问题
isVaild函数判断每次寻找的上下左右四个坐标是否合规。
终点判断为(n-1,m-1),因为我的遍历是从(0,0)点开始的。
代码模板
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;const int N=110;
typedef pair<int,int>PII;int map[N][N];
int far[N][N];int n,m;bool isVaild(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}int bfs(int a,int b)
{queue <PII> q;q.push({a,b});far[a][b]=0;int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};while(!q.empty()){PII cell=q.front();q.pop();int x=cell.first;int y=cell.second;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(isVaild(nx,ny)&&map[nx][ny]==0&&far[nx][ny]==5000){far[nx][ny]=far[x][y]+1;q.push({nx,ny});if(nx==n-1&&ny==m-1)return far[nx][ny];}}}return 0;
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>map[i][j];far[i][j]=5000;}}int dis=bfs(0,0);cout<<dis<<endl;return 0;
}