Acid_answer
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...