1 条题解

  • 0
    @ 2024-6-1 14:35:12

    和走迷宫类似的广搜,难点在于对传送点的处理,一旦走到一个传送点,马上将坐标移动到另一个传送点

    #include<bits/stdc++.h>
    using namespace std;
    const int N=305;
    int n,m,k,s,t,a[N][N],d[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    int ex,ey,sx,sy;
    pair<int,int> h[200];//A   h['A']  h['A'+26]
    char c[N][N];
    queue<pair<int,int>> q;
    int bfs(int sx,int sy){
    	memset(d,0x3f,sizeof(d));
    	d[sx][sy]=0;
    	q.push({sx,sy});
    	while (!q.empty()){
    		int x=q.front().first;
    		int y=q.front().second;
    		q.pop();
    		if (x==ex && y==ey) return d[x][y];
    		for (int i=0;i<4;++i){
    			int _x=x+dx[i];
    			int _y=y+dy[i];
    			char ch=c[_x][_y];
    			if (_x>=1 && _x<=n && _y>=1 && _y<=m && ch!='#'){
    				if (ch>='A' && ch<='Z') {
    					if (h[ch]==make_pair(_x,_y)) _x=h[ch+26].first,_y=h[ch+26].second;	
    					else _x=h[ch].first,_y=h[ch].second;
    				}
    				if (d[_x][_y]>d[x][y]+1) {
    					d[_x][_y]=d[x][y]+1;
    					q.push({_x,_y});
    				}
    			} 
    		}			
    	}
    	return -1;
    }
    int main(){
    //	freopen("in.txt","r",stdin);
    	int x,y;
    	cin>>n>>m;
    	for (int i=1;i<=n;++i){
    		cin>>c[i]+1;
    		for (int j=1;j<=m;++j)
    			if (c[i][j]=='@') sx=i,sy=j;
    			else if (c[i][j]=='=') ex=i,ey=j;
    			else if (c[i][j]>='A' && c[i][j]<='Z'){
    				if (h[c[i][j]]==make_pair(0,0)) h[c[i][j]]={i,j};
    				else h[c[i][j]+26]={i,j}; 
    			}
    	}
    	cout<<bfs(sx,sy);
    }
    
    • 1

    [USACO11OPEN] Corn Maze S【难】

    信息

    ID
    767
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    183
    已通过
    34
    上传者