Untitled

mail@pastecode.io avatar
unknown
plain_text
22 days ago
1.8 kB
1
Indexable
Never
#include<iostream>
using namespace std;

int mover[8]={-2,-1,1,2,2,1,-1,-2};
int movec[8]={1,2,2,1,-1,-2,-2,-1};
int movekr[8]={-1,-1,0,1,1,1,0,-1};
int movekc[8]={0,1,1,1,0,-1,-1,-1};

struct point{
	int x,y;
};

char map[100][100];
int t,m,n,xa,ya,xb,yb;
int visit[100][100];

void resetvisit(){
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++) visit[i][j]=-1;
	}
}

class queue{
	int rear, front;
	point mang[10000];
public:
	queue(){
		rear=front=-1;
	}
	void push(point a){
		rear++;
		mang[rear].x=a.x; mang[rear].y=a.y;
	}
	point pop(){
		front++;
		return mang[front];
	}
	bool isempty(){
		return (rear==front);
	}
	void reset(){
		rear=front=-1;
	}
};

queue q;

void bfs(point a){
	q.push(a);
	visit[a.x][a.y]=0;
	while(!q.isempty()){
		point v=q.pop();
		for(int h=0;h<8;h++){
			point u;
			u.x=v.x+movekr[h]; u.y=v.y+movekc[h];
			if(u.x>=0 && u.x<m && u.y>=0 && u.y<n && visit[u.x][u.y]==-1 && map[u.x][u.y]!='Z' && map[u.x][u.y]!='z'){
				visit[u.x][u.y]=visit[v.x][v.y]+1;
				q.push(u);
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> m >> n;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				cin >> map[i][j];
				if(map[i][j]=='A'){
					xa=i; ya=j;
				}
				else if(map[i][j]=='B'){
					xb=i; yb=j;
				}
			}
		}
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(map[i][j]=='Z'){
					for(int h=0;h<8;h++){
						int ni=i+mover[h]; int nj=j+movec[h];
						if(ni>=0 && ni<m && nj>=0 && nj<n && map[ni][nj]=='.') map[ni][nj]='z';
					}
				}
			}
		}
		point a,b;
		a.x=xa; a.y=ya; b.x=xb; b.y=yb;
		resetvisit();
		q.reset();
		bfs(a);
		if(visit[xb][yb]==-1) cout << "-1" << endl;
		else cout << visit[xb][yb] << endl;
	}


	return 0;
}
Leave a Comment