7分求助,BFS打炸了样例还是没输出……
查看原帖
7分求助,BFS打炸了样例还是没输出……
523541
wdy1028楼主2021/10/11 21:28
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int INF = 2147483647;
char a[305][305];
int tp[305][4],fx,fy,ex,ey,n,m;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
struct node{int x,y,dis;};
inline void bfs()
{
	queue <node> q;
	node start;
	start.x = fx,start.y = fy,start.dis = 0;
	q.push(start);
	while(!q.empty())
	{
		start = q.front();q.pop();
		for(int i = 0;i < 4;++i)
		{
			int nx = start.x+dx[i],ny = start.y+dy[i],ndis = start.dis+1;
			if(nx == ex && ny == ey) {printf("%d\n",ndis);return;}
			if(a[nx][ny] == '#' || nx < 1 || nx > n || ny < 1 || ny > m) continue;
			if(a[nx][ny] == '.') q.push({nx,ny,ndis}),a[nx][ny] = '#';
			else if('A' <= a[nx][ny] && a[nx][ny] <= 'Z')
			{
				if(nx == tp[a[nx][ny]][0] && ny == tp[a[nx][ny]][1])
					q.push({tp[a[nx][ny]][0],tp[a[nx][ny]][1],ndis});
				else if(nx == tp[a[nx][ny]][3] && ny == tp[a[nx][ny]][4])
					q.push({tp[a[nx][ny]][2],tp[a[nx][ny]][3],ndis});	
				for(int j = 0;j < 4;++j) tp[a[nx][ny]][j] = '#';	
			}
		}
	}
}
inline LL read()
{
	LL x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
int main(int argc,char *argv[])
{ 
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	n = read(),m = read();
	for(int i = 0;i <= 29;++i)
		for(int j = 0;j < 4;++j) tp[i][j] = '&';
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
		{
			cin>>a[i][j];
			if(a[i][j] == '@') fx = i,fy = j;
			if(a[i][j] == '=') ex = i,ey = j;
			if('A' <= a[i][j] && a[i][j] <= 'Z')
			{
				if(tp[a[i][j]-'A'][0] == '&') 
				{
					tp[a[i][j]][0] = i;
					tp[a[i][j]][1] = j;
				}
				else
				{
					tp[a[i][j]][2] = i;
					tp[a[i][j]][3] = j;
				}
			}
		}
	bfs();
	//printf("Time used = %.0lfms\n",((double)clock()/(double)CLOCKS_PER_SEC) * 1000.0);
	return 0;
}  
2021/10/11 21:28
加载中...