Untitled
unknown
plain_text
2 years ago
12 MB
6
Indexable
//grid axit
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
typedef long long int lli;
int n, m, x, y, x_2, y_2, sum_2, sum_1;
int arr[3001][3001], vs[3001][3001], queue_i[9000000], queue_j[9000000];
int Xd[4] = {1,-1,0,0}, Yd[4]={0,0,1,-1};
void check_2(){
for(int i = 0; i< 4; i++){
int X = x_2 + Xd[i], Y = y_2 + Yd[i];
if(X >= 1 && X <= n && Y >= 1 && Y <= m){
if(vs[X][Y] == 0){
sum_2 = -1;
sum_1 = -1;
break;
}
else{
sum_2 = max(sum_2, vs[X][Y]);
}
}
}
if(sum_2!=-1){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(arr[i][j]==1){
if(vs[i][j]==0){
sum_1= -1; break;
}
else {
sum_1 = max(sum_1, vs[i][j]);
}
}
}
if(sum_1==-1) break;
}
}
}
void bfs(){
int front = 0, rear = 0;
vs[x][y] = 1;
queue_i[rear] = x; queue_j[rear] = y;
rear++;
while (front != rear){
int g = queue_i[front], h = queue_j[front];
front++;
for(int i = 0; i< 4; i++){
int X = g + Xd[i], Y = h + Yd[i];
if(X >= 1 && X <= n && Y >= 1 && Y <= m && !vs[X][Y] && arr[X][Y] == 1) {
queue_i[rear] = X;
queue_j[rear] = Y;
rear++;
vs[X][Y] = vs[g][h]+1;
//sum_1 = max(sum_1, vs[X][Y]);
}
}
}
}
int main(){
freopen("ip.txt", "r", stdin);
ios::sync_with_stdio(false);
int t;
cin >> t;
for(int tc = 1; tc <= t; tc++){
cin >> n >> m;
cin >> x >> y;
x_2 = -1; y_2 = -1;
sum_2 = 0;
sum_1 = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> arr[i][j];
vs[i][j] = 0;
if(arr[i][j]==2){
x_2 = i;
y_2 = j;
}
}
}
cout << "Case #" << tc << endl;
for(int i = 0; i< 4; i++){
int X = x_2 + Xd[i], Y = y_2 + Yd[i];
if(X < 1 || X > n || Y < 1 || Y > m) {
sum_2 = -1;
cout << -1 << " " << -1 << endl;
break;
}
}
if(sum_2!=-1){
bfs();
check_2();
cout << sum_2 << " " << sum_1 <<