BFS 43求调。
查看原帖
BFS 43求调。
937690
111216dzy楼主2023/2/11 21:57
#include <bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,m; 
char cs[303][303];
struct node{
	int x,y,step;
}root,q[90010];
bool vis[303][303];
int f=1,t=0;
int fi(bool type,int x,int y){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(cs[x][y]==cs[i][j]&&(x!=i||y!=j)){
//				cout<<x<<" "<<y<<" "<<i<<" "<<j<<endl;
				if(type==0)return j;
				else return i;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	vis[n][m]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf(" %c",&cs[i][j]);
			if(cs[i][j]=='@')root.x=i,root.y=j;
		}
	q[++t]=root;	
	while(f<=t){
		node u=q[f++],v;
		for(int i=1;i<=4;i++){
			v=u;
			v.step++,v.x+=dx[i],v.y+=dy[i];
			if(v.x<1||v.x>n||v.y<1||v.y>m)continue;
			if(cs[v.x][v.y]=='#')continue;
			if(vis[v.x][v.y])continue;
			vis[v.x][v.y]=1;
			if(cs[v.x][v.y]<='Z'&&cs[v.x][v.y]>='A')v.x=fi(1,v.x,v.y),v.y=fi(0,v.x,v.y);
			q[++t]=v;
			if(cs[v.x][v.y]=='='){
				cout<<v.step;
				return 0;
			}
		}
	}
    return 0;
}

样例没输出,改了好久,只有43分。

2023/2/11 21:57
加载中...