helpppppppppppppppp
  • 板块灌水区
  • 楼主cyfcyf
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/20 19:43
  • 上次更新2023/11/4 03:08:32
查看原帖
helpppppppppppppppp
545642
cyfcyf楼主2021/10/20 19:43

老鼠走迷宫求最短路径用BFS怎么做啊,做到一半做不来了,附上我的代码,谢谢各位大神援助

#include<bits/stdc++.h>
using namespace std;
 
int graph[50][50];
int n,m;
int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
int vis[50][50],dis[50][50];

bool isLegal(int x, int y){
	return x>=1&&y>=1&&x<n&&y<m&&vis[x][y];
}

int BFS(int xx,int yy){
	queue<int> qx,qy;
	vis[xx][yy]=0;
	qx.push(xx);
	qy.push(yy);
	while(!qx.empty()){
	   int mx=qx.front();
	   int my=qy.front();
	   qx.pop();
	   qy.pop();
	   for(int i=1;i<=4;i++){
	      if(mx==n&&my==m)  return dis[mx][my];
	      int nx=dx[i]+mx,ny=dy[i]+my;
	      if(isLegal(nx,ny)){
	         dis[nx][ny]=dis[mx][my]+1;
                 qx.push(nx);
	         qy.push(ny); 
		vis[mx][my]=0;
			}
		}
	}
	return -1;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			vis[i][j]=0;
		}
	}
		
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>graph[i][j];
			vis[i][j]=graph[i][j];
		}
	}
	cout<<BFS(1,1)<<endl;
	return 0;
}
2021/10/20 19:43
加载中...