2TLE 2WA 73分 玄关求调
查看原帖
2TLE 2WA 73分 玄关求调
778070
tall_buildin楼主2025/1/15 14:34
#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[310][310];
struct dow{
	int x,y;
	int step;
};
struct door{
	int x1,x2;
	int y1,y2;
};
dow qsd;
door d[91];
int dx[5] = {0,1,-1,0,0};
int dy[5] = {0,0,0,-1,1};
void bfs(){
	queue<dow> q;
	q.push(qsd);
	while(!q.empty()){
		dow jnow = q.front();
		q.pop();
		for (int i = 1;i<=4;i++){
			dow now = jnow;
			int nx = now.x+=dx[i];
			int ny = now.y+=dy[i]; 
			if (a[nx][ny] == '='){
				now.step+=1;
				cout<<now.step;
				return;
			}
			if (a[nx][ny] == '#')	continue;
			if (a[nx][ny] == '.'){
				now.x = nx;
				now.y = ny;
				now.step+=1;
				q.push(now);
				a[nx][ny] = '#';
			}
			if ((int)a[nx][ny]>=65 && (int)a[nx][ny]<=90){ 
				if (d[ (int)a[nx][ny]].x2 == nx){
					now.x = d[(int)a[nx][ny]].x1;
					now.y = d[(int)a[nx][ny]].y1;
					now.step+=1;
					q.push(now);
				}
				else{
					now.x = d[(int)a[nx][ny]].x2;
					now.y = d[(int)a[nx][ny]].y2;
					now.step+=1;
					q.push(now);
				}
			}
		}
		
	}
}

int main(){
    cin>>n>>m;
    memset(a,'#',sizeof(a));
    for (int i = 1;i<=n;i++)
        for (int j = 1;j<=m;j++){
			cin>>a[i][j];
			if (a[i][j] == '@')
				qsd.x = i,qsd.y = j,qsd.step = 0,a[i][j] = '#';
			if ((int)a[i][j]>=65 && (int)a[i][j]<=90){
				if (d[(int)a[i][j]].x1>0){
					d[(int)a[i][j]].x2 = i,
					d[(int)a[i][j]].y2 = j;
				}
				else{
					d[(int)a[i][j]].x1 = i,
					d[(int)a[i][j]].y1 = j;
				}
			}	
        }
    bfs();
    
    return 0;
}
2025/1/15 14:34
加载中...