Acid_answer

 avatar
unknown
plain_text
2 years ago
1.6 kB
6
Indexable
#include <iostream>
using namespace std;

int in[302][302];
int Qx[100000];
int Qy[100000];
int r = -1, f = -1;
int dx[4]= {1,0,0,-1};
int dy[4]= {0,1,-1,0};
void push(int x, int y){
	r++;
	Qx[r] = x;
	Qy[r] = y;
}
void pop(int &x, int &y){
	f++;
	x = Qx[f];
	y = Qy[f];
}
void BFS(int x, int y, int n, int m){
	push(x,y);
	int t = 0;
	int t_fill = 0;
	int check = 0;
	while(r != f){
		int r1 =r;
		int f1 =f;
		for(int i  = 0; i < r1 -f1 ; i++){
			pop(x,y);
			in[x][y] = 0;
		for(int j = 0; j < 4; j++ ){
			int x1 = x + dx[j];
			int y1 = y + dy[j];
			if(in[x1][y1] == 1){
				push(x1,y1);
			}
			if(in[x1][y1] == 2){
				check++;
				if(check == 4){
					t_fill = t+1;
				}
			}
		}
		}
		t++;
	}
	int all_fill = 0;
	for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j++){
				if(in[i][j] == 1){
					all_fill = 1;
					break;
				}
			}
		}
	if(check == 4) cout << t_fill << " ";
	else if(check != 4) cout << -1 << " ";
	if(all_fill == 0) cout << t<< endl;
	else if(all_fill == 1) cout << -1  << endl;

}
int main(){
	freopen ("input.txt","r", stdin);
	int T;
	cin >> T;
	r = -1;
	f = -1;
	for(int tc = 1; tc <= T; tc++){
		int n, m;
		int x,y;
		cin >> n >> m;
		cin >> x >> y;
		for(int i = 0; i <= n+1; i ++){
			for(int j = 0; j <= m+1; j++){
				in[i][j] = 0;
			}
		}
		int x1, y1;
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j++){
				cin >> in[i][j];
				if(in[i][j] == 2){
					x1 = i;
					y1 = j;
				}
			}
		}
		cout << "Case #" << tc << endl;
		BFS(x,y,n,m);
	}
	return 0;
}
Editor is loading...