Submission #1357735

#TimeUsernameProblemLanguageResultExecution timeMemory
1357735vjudge1Robots (APIO13_robots)C++17
30 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
    int a,b,c,d,e,f[15][15][4],x1,x2,y11,y2,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},hm[105][105];
    char ch[15][15];
void dfs(int x,int y,int z){
	if(f[y][x][z]!=-1) return;
//	cout<<x<<' '<<y<<' '<<z<<endl;
	int nz=z;
    if(ch[y][x]=='C') nz=(z+1)%4;
    if(ch[y][x]=='A') nz=(z+3)%4;
    int nx=x+dir[nz][1],ny=y+dir[nz][0];
    if(nx>=0 and nx<b and ny>=0 and ny<c and ch[ny][nx]!='x'){
        dfs(nx,ny,nz);
        f[y][x][z]=f[ny][nx][nz];
    }
    else f[y][x][z]=10*y+x;
}
int main(){
    cin>>a>>b>>c;
    queue<pair<int,int>>q;
    for(int i=0;i<4;i++){
//    	cout<<dir[i][0]<<' '<<dir[i][1]<<endl;
	}
    for(int i=0;i<c;i++){
        for(int h=0;h<b;h++){
        	for(int j=0;j<4;j++) f[i][h][j]=-1;
            cin>>ch[i][h];
            if(ch[i][h]=='1'){
                x1=h;
                y11=i;
            }
            if(ch[i][h]=='2'){
                x2=h;
                y2=i;
            }
        }
    }
    for(int i=0;i<c;i++){
        for(int h=0;h<b;h++){
            for(int j=0;j<4;j++){
                if(f[i][h][j]==-1){
                    dfs(h,i,j);
//                    cout<<"||||||||||||\n";
                }
//                cout<<i<<' '<<h<<' '<<j<<' '<<f[i][h][j]<<endl;
            }
        }
    }
//    cout<<"|||||||||||||||||||||||||||||||||\n";
    q.push({10*y11+x1,10*y2+x2});
    for(int i=0;i<=100;i++){
    	for(int h=0;h<=100;h++){
    		hm[i][h]=-1;
		}
	}
	hm[10*y11+x1][10*y2+x2]=0;
    while(!q.empty()){
    	int q1=q.front().first,q2=q.front().second;
    	if(q1==q2){
//    		cout<<q1<<' '<<q2<<"\n";
    		cout<<hm[q1][q2]<<"\n";
    		return 0;
		}
    	int yf=q1/10,xf=q1%10,ys=q2/10,xs=q2%10;
    	for(int i=0;i<4;i++){
    		int q11=f[yf][xf][i];
    		int q22=f[ys][xs][i];
    		if(hm[q11][q2]==-1){
//    			cout<<q1<<' '<<q2<<' '<<q11<<' '<<q2<<"\n";
    			hm[q11][q2]=hm[q1][q2]+1;
    			q.push({q11,q2});
			}
			if(hm[q1][q22]==-1){
//    			cout<<q1<<' '<<q2<<' '<<q1<<' '<<q22<<"\n";
    			hm[q1][q22]=hm[q1][q2]+1;
    			q.push({q1,q22});
			}
		}
		q.pop();
	}
	cout<<-1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...