bfs TLE5个点求调,这为啥会被卡...
查看原帖
bfs TLE5个点求调,这为啥会被卡...
1051584
Crushxl楼主2024/3/16 20:06
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=305,INF=0x7f7f7f7f;
int n,m,sx,sy,fx,fy,g[MAXN][MAXN],ans[MAXN][MAXN];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool vis[MAXN][MAXN];
struct node{int x,y,t;};
struct portal{char ch;int x,y;};
queue<node> q;
vector<portal> pt;

pair<int,int> teleport(char ch,int x,int y){
	pair<int,int> c;
	for(int i=0;i<pt.size();i++){
		if(pt[i].ch==ch && (pt[i].x!=x||pt[i].y!=y)){
			return make_pair(pt[i].x,pt[i].y);
		}
	} 
}

int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		string str;
		cin >> str;
		for(int j=0;j<m;j++){
			g[i][j+1] = str[j];
			if(str[j] == '@'){
				sx=i,sy=j+1;
			}else if(str[j] == '='){
				fx=i,fy=j+1;
			}else if(isalpha(str[j])){
				pt.push_back({str[j],i,j+1});
			}
		}
	}
	fill(ans[0],ans[0]+MAXN*MAXN,INF);
	q.push({sx,sy,0});
	while(!q.empty()){
		node tmp = q.front();
		int x=tmp.x,y=tmp.y,t=tmp.t;
		vis[x][y] = 1;
		q.pop();
		if(g[x][y] == '='){
			cout << t;
			return 0;
		}
		if(isalpha(g[x][y])){
			vis[x][y] = 0;	//进入传送门时不标记 
			pair<int,int> c = teleport(g[x][y],x,y);
			x=c.first,y=c.second;
		}
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				if(!vis[nx][ny] && g[nx][ny]!='#'){
					q.push({nx,ny,t+1});
					ans[nx][ny] = min(ans[nx][ny],t+1);
				}
			}
		}
	}
}
2024/3/16 20:06
加载中...