#include<bits/stdc++.h> 
using namespace std;
struct node{
	int x,y;
}; 
int n,m,sx=1,sy=1;//sx,sy作为起点坐标 
int a[1005][1005]; //用于存储地图 
int step[1005][1005]; //step[x][y]代表从起点走到(x,y)最少要花几步 
int vis[1005][1005]; //用于检测(x,y)点是否走过,如果走过设为1 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//上下左右四个方向预先处理 
void bfs(){
	queue<node> q;
	q.push({sx,sy});
	vis[sx][sy]=1;//起点先入队,作为第一个被处理的点
	while(!q.empty()){
		//处理队首元素 
		int x = q.front().x;
		int y = q.front().y;
		//我们要处理的点是(x,y),我们要对其进行扩散 
		q.pop();//该点处理完毕后出队,免得死循环
		for(int i=0;i<4;i++){
			int tx = x+dx[i]*a[x][y];
			int ty = y+dy[i]*a[x][y];//(tx,ty)是即将被扩散的点
			if(tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]!='#' && vis[tx][ty]==0){//边界判断,每个点只需要走到一次
				q.push({tx,ty});//下一层元素入队
				vis[tx][ty]=1;//标记
				step[tx][ty] = step[x][y]+1;//记录步数
			} 
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	bfs();//广搜处理step数组
	if(step[n][m]==0) cout << "No Solution";
	else cout << step[n][m];
	return 0;
} 

0 条评论

目前还没有评论...