社区讨论

59求助

P1825[USACO11OPEN] Corn Maze S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@luuwnfr7
此快照首次捕获于
2024/04/11 15:15
2 年前
此快照最后确认于
2024/04/11 18:16
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
char mp[310][310];  //地图 
bool vis[310][310]; //染色图 
int dirx[]={0,1,0,-1}; //4个方向 
int diry[]={1,0,-1,0};
struct AXI{
	int x,y;
}ax;
int n,m;
queue<AXI> qu;
bool judge(int x,int y){
	if(x<1||y<1||x>n||y>m){ //超界 
		return false;
	}else if(vis[x][y]||mp[x][y]=='#'){ //走过和碰到障碍 
		return false;
	}else{
		return true;
	}
}
void BFS(){
	int step=0;
	while(!qu.empty()){
		int len=qu.size();
		while(len--){
		    
			//找到出口,输出步数,结束程序 
			if(mp[qu.front().x][qu.front().y]=='='){ 
				cout<<step;
				return ;
			}
			
			//找到传送装置,更新当前队头的坐标 
			if(mp[qu.front().x][qu.front().y]>='A'&&mp[qu.front().x][qu.front().y]<='Z'){ //找到传送装置 
				vis[qu.front().x][qu.front().y]=true;
				for(int i=1;i<=n;i++){
					for(int j=1;j<=m;j++){
						if(mp[i][j]==mp[qu.front().x][qu.front().y]&&!vis[i][j]){ //更新这一点 
							qu.front().x=i;
							qu.front().y=j;
						}
					}
				}
			}
			
			for(int i=0;i<4;i++){  //4个方向扫描 
				int tx=qu.front().x+dirx[i];
			    int ty=qu.front().y+diry[i];
				if(judge(tx,ty)){
					vis[tx][ty]=true;
					ax.x=tx;
					ax.y=ty;
					qu.push(ax);
				}
			}
			qu.pop(); 
		}
		step++;
	}
}
int main() {
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		cin>>mp[i][j];
    	}
    }
    for(int i=1;i<=n;i++){ //找起点入队 
    	for(int j=1;j<=m;j++){
    		if(mp[i][j]=='@'){
    			vis[i][j]=true;
    			ax.x=i;
    			ax.y=j;
    			qu.push(ax);
    			break;
    		}
    	}
    }
    BFS();
    
    
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...