#include<bits/stdc++.h> 
using namespace std;
struct node{
	int x,y;
}; 
int n,m,sx=1,sy=1;//sx,sy作为起点坐标 
char a[1005][1005]; //用于存储地图 
int step[1005][1005]; //step[x][y]代表从起点走到(x,y)最少要花几步 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//上下左右四个方向预先处理 
void bfs(){
	deque<node> dq;
  //用双端队列,如果走到.上则优先插入到队首进行优先扩散
  //走到 * 上则插入到队尾,最后处理
	dq.push_front({sx,sy});
	memset(step,0x3f,sizeof(step));
	step[1][1]=0;
	//0x3f3f3f3f
	while(!dq.empty()){
		int x = dq.front().x;
		int y = dq.front().y;
		dq.pop_front();
		for(int i=0;i<4;i++){
			int tx = x+dx[i];
			int ty = y+dy[i];//vis
			if(tx>=1 && tx<=n && ty>=1 && ty<=m && step[tx][ty]==0x3f3f3f3f){
				int cost = (a[tx][ty]=='*') ; 
				//满足条件则证明该点没来过 
				step[tx][ty] = step[x][y] + cost;
				if(cost==0)  dq.push_front({tx,ty});
				else dq.push_back({tx,ty});
			}
		}
	}
}
int main(){
	cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    bfs();
    cout << step[n][m];
	return 0;
} 

0 条评论

目前还没有评论...