65分TLE,求助
查看原帖
65分TLE,求助
114154
陆朱良雨楼主2024/7/27 17:01
#include<bits/stdc++.h>
using namespace std;
#define N 501
#define INF 999999999
int n,m,switcx[26][2],switcy[26][2],minstep[N][N],sx,sy,ex,ey,gox[4]={0,0,1,-1},goy[4]={1,-1,0,0},tox,toy,sum[26];
string s;
char mapn[N][N];
queue<int>qx,qy,qs;
bool findgate(int x,int y) {
	for(int i=0;i<26;i++) 
		for(int j=0;j<2;j++)
			{
				if(switcx[i][j]==x&&switcy[i][j]==y) {
					tox=switcx[i][1-j];toy=switcy[i][1-j];return 1;
				}
			}
	return 0;
}
void bfs(int ssx,int ssy,int ssstep) {
	qx.push(ssx);qy.push(ssy);qs.push(ssstep);
	while(!qx.empty()) {
		int x=qx.front(),y=qy.front(),s=qs.front();
		qx.pop();qy.pop();qs.pop();
		minstep[x][y]=min(minstep[x][y],s);
		if(x==ex&&y==ey) return;
		for(int i=0;i<4;i++) {
			int xx=x+gox[i],yy=y+goy[i];
			if(xx<1||yy<1||xx>n||yy>m||((minstep[xx][yy]<=s+1)&&(!findgate(xx,yy)))||mapn[xx][yy]=='#') continue;
			if(findgate(xx,yy)) {
				qx.push(tox);qy.push(toy);qs.push(s+1);
			//	minstep[xx][yy]=min(minstep[xx][yy],s+1);
			}
			else{
				qx.push(xx);qy.push(yy);qs.push(s+1);
			}
		}
	}
	return;
}
void print() {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) cout<<mapn[i][j];
		cout<<endl;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(minstep[i][j]!=INF) cout<<minstep[i][j]<<" ";
			else cout<<"* "; 
		}
		cout<<endl;
	}
	return;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>s;
		for(int j=1;j<=m;j++) {
			minstep[i][j]=INF;
			mapn[i][j]=s[j-1];
			if(s[j-1]=='@') {
				sx=i;sy=j;
			}
			if(s[j-1]=='=') {
				ex=i;ey=j;
			}
			if(s[j-1]>='A'&&s[j-1]<='Z') {
				int tmp=s[j-1]-'A';
				if(sum[tmp]<2) switcx[tmp][sum[tmp]]=i;
				if(sum[tmp]<2) switcy[tmp][sum[tmp]]=j;
				sum[tmp]++;
			}
		}
	}
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++) 
	 	if(mapn[i][j]>='A'&&mapn[i][j]<='Z'&&sum[mapn[i][j]-'A']!=2)
	 		mapn[i][j]='.';
	minstep[sx][sy]=0;
	bfs(sx,sy,0);
	cout<<minstep[ex][ey]<<endl;
	//print();//
	return 0;
} 
2024/7/27 17:01
加载中...