Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
#include<iostream>
using namespace std;
const int MAXS = 50000;
int Qx[MAXS];
int Qy[MAXS];
int map[3001][3001];
int visited[3001][3001] = {0};
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int rear, front,m,n,xT,yT,xE,yE;
int cnt1, cnt2,step;

void push(int x, int y){
	if(rear == MAXS -1) rear = -1;
	rear++;
	Qx[rear] = x;
	Qy[rear] = y;
}

void pop(){
	if(front == MAXS -1) front = -1;
	front++;
}
bool isEmpty(){
	return rear == front;
}
int check(int i, int j){
	int max =-1;
	for(int h =0;h<4;h++){
		int x = i + dx[h];
		int y = j + dy[h];
		if(visited[x][y] == 0){
			return 0;
		}
		if(visited[x][y] >= max){
			max = visited[x][y];
		}
	}
	return max;
}
void bfs(){
	step = 1;
	while (!isEmpty())
	{
		pop();
		int i = Qx[front];
		int j = Qy[front];
		for(int h = 0;h<4;h++){
			int x = i + dx[h];
			int y = j + dy[h];
			if(x>= 0 && x<m && y>=0 && y<n){
				if(map[x][y] == 1 && visited[x][y] == 0){
					visited[x][y] = visited[i][j] +1;
					if(visited[x][y]>step) step = visited[x][y];
					push(x,y);
				}
			}
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	int tc; cin>>tc;
	for(int ts =1;ts<=tc;ts++){
		front = rear =-1;
		bool flag = 0, flag2 = 1;
		cout<<"Case #"<<ts<<endl;
		int xx,yy;
		cin>>m>>n>>xx>>yy;
		xT = xx -1;
		yT = yy -1;
		push(xT,yT);
		for(int i =0;i<m;i++){
			for(int j=0;j<n;j++){
				cin>>map[i][j];
				visited[i][j] = 0;
				if(map[i][j] == 2){
					yE = j;
					xE = i;
					if(i == 0 && j == 0 ||i == m-1 && j == 0||i == 0 && j == n-1||i == m-1 && j == n-1){
						flag = 1;
					}
				}
			}
		}
		visited[xT][yT] = 1;
		bfs();
		for(int i = 0;i<m;i++){
			for(int j =0;j<n;j++){
				if(visited[i][j] == 0 && map[i][j] != 0 && map[i][j] != 2){
					flag2 = 0;
				}
			}
		}
		if(flag ||check(xE,yE) == 0){
			cout<<-1<<" "<<-1<<endl;
		}
		else
		{
			if(flag2)
				cout<<check(xE,yE)<<" "<<step<<endl;
			else
				cout<<check(xE,yE)<<" "<<-1<<endl;
		}
	}
	return 0;
}