玄学bfs
查看原帖
玄学bfs
906854
cqbzcjh楼主2024/8/16 10:23
#include<bits/stdc++.h>
using namespace std;
#define x first 
#define y second
const int N=305;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,ans[N][N],ex,ey;
bool vis[N][N];
char a[N][N];
typedef pair<int,int> PII;
void bfs(){
	queue<PII> q;
	q.push({sx,sy});
//	cout<<sx<<" "<<sy<<"\n";
	while(!q.empty()){
		PII u=q.front();
		q.pop();
		if(a[u.x][u.y]=='='){
			ex=u.x;
			ey=u.y;
			return;
		}
		if('A'<=a[u.x][u.y]&&a[u.x][u.y]<='Z'){
//			cout<<-1<<'\n';
			int f=0;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(i==u.x&&j==u.y)continue;
					if(a[i][j]==a[u.x][u.y]){
						ans[i][j]=ans[u.x][u.y];
						u.x=i;
						u.y=j;
						f=1;
//						cout<<u.x<<" "<<u.y<<"\n";
						break;
					}
				}
				if(f)break;
			}
		}
//		cout<<u.x<<" "<<u.y<<"\n";
		for(int i=0;i<4;i++){
			int tx=u.x+dx[i],ty=u.y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m)continue;
			if(a[tx][ty]=='#')continue;
			if(vis[tx][ty])continue;
			q.push({tx,ty});
			vis[tx][ty]=1;
			ans[tx][ty]=ans[u.x][u.y]+1;
		}
	}
}
int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				sx=i;
				sy=j;
			}
		}
	}
	bfs();
	cout<<ans[ex][ey];
	return 0;
}

这是我将答案单独存在一个数组的方式,WA on #15

#include<bits/stdc++.h>
using namespace std;
const int N=305;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,ex,ey;
bool vis[N][N];
char a[N][N];
struct node{
	int x,y,step;
};
void bfs(){
	queue<node> q;
	q.push({sx,sy,0});
	while(!q.empty()){
		node u=q.front();
		q.pop();
		if(a[u.x][u.y]=='='){
			cout<<u.step;
			return;
		}
		if('A'<=a[u.x][u.y]&&a[u.x][u.y]<='Z'){
			int f=0;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(a[i][j]==a[u.x][u.y]&&(i!=u.x||j!=u.y)){
						u.x=i;
						u.y=j;
						f=1;
						break;
					}
				}
				if(f)break;
			}
		}
		for(int i=0;i<4;i++){
			int tx=u.x+dx[i],ty=u.y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m)continue;
			if(a[tx][ty]=='#')continue;
			if(vis[tx][ty])continue;
			q.push({tx,ty,u.step+1});
			vis[tx][ty]=1;
		}
	}
}
int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				sx=i;
				sy=j;
			}
		}
	}
	bfs();
	return 0;
}

但是当我直接在结构体里存时就 AC 了

蒟蒻求大佬帮忙看一下第一份代码有什么问题QWQ

2024/8/16 10:23
加载中...