1 条题解

  • 3
    @ 2026-7-26 14:53:42
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,ans=0x3f3f3f3f,sx,sy,ex,ey;
    char a[25][25];
    int dx[]={0,1,0,-1};
    int dy[]={1,0,-1,0};
    bool check(int x,int y){
    	if(x<=0 || y<=0 || x>n || y>m){
    		return false;
    	}
    	if(a[x][y]=='#'){
    		return false;
    	}
    	return true;
    }
    void dfs(int x,int y,int t){
    	if(ans<t) return;
    	if(x==ex && y==ey){
    		ans=min(ans,t);
    		return;
    	}
    	for(int i=0;i<4;++i){
    		int nx=x+dx[i],ny=y+dy[i];
    		if(check(nx,ny)){
    			int temp=1;
    			if(a[nx][ny]=='x'){
    				temp++;
    			}
    			a[nx][ny]='#';
    			t+=temp;
    			dfs(nx,ny,t);
    			t-=temp;
    			a[nx][ny]=(temp & 1 ? '@' : 'x');
    		}
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;++i){
    		for(int j=1;j<=m;++j){
    			cin>>a[i][j];
    			if(a[i][j]=='r'){
    				sx=i;sy=j;
    			}
    			if(a[i][j]=='a'){
    				ex=i;ey=j;
    			}
    		}
    	}
    	a[sx][sy]='#';
    	dfs(sx,sy,0);
    
    	if(ans==0x3f3f3f3f){
    		cout<<"Impossible";
    		return 0;
    	}
    	cout<<ans;
    	return 0;
    }
    • 1

    信息

    ID
    207
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    6
    已通过
    5
    上传者