Grid Acid
Ann
c_cpp
2 years ago
7.2 kB
7
Indexable
Grid Acid
A rectangular grid has N x M size. Each cell is either made of a special metal(type A) or made of stone (type B).
If acid is poured on a cell of grid, it can either melt it(for type A: special metal cell) and spread further or do not pass through it(for type B: stone cell).
The cell made with special metal (type A) can melt with acid in 1 second and thus allow acid to spread further.
The cell made with stone (type B) does not react with acid and hence neither melt nor allow acid to pass through it.
There is a third type of a cell that is empty (type C), but has a boundary (all 4 sides) covered with a protective metal.
Fig. A grid of 7 x 8 size as example
If all 4 sides of it (type C: empty cell) come into contact with acid at any given time, then in that case boundary of it (all 4 sides)melt and allow acid to pass through it. In that case it (type C: empty cell) get filled with acid.
There is only one and only one such cell in a given grid.
Acid is poured on one of the cell of grid, the cell being made of special metal that can melt with acid.
It is guaranteed that acid will be poured on only one cell made up of special metal (type A), not on the stone (type B) or the empty cell(type C).
Acid is poured continuously until all the grid cells (except stone - type B) melt completely.
You have to tell when the empty cell with special protective boundary will get filled with acid and when whole grid will get filled with acid (except the cells made up of stones).
It takes 1sec for acid to dissolve special metal cell and after that it can spread to its 4 orthogonal neighbors (Left, Right, Up, Down).
Input:
First entry is number of test cases; rest is each test case input.
For each test case first row contains N and M as two integers separated by a space.
Next row contains the location of cell (row and column number separated by space) where acid will be poured continuously until whole grid (except stone cells) melt.
Next N rows contain M integer values each containing the cell type.
Cell type value is of 3 types:
- 0 : cell is stone (type B)
- 1: cell is made special metal (type A)
- 2: cell is special empty cell, having a special boundary (type C)
Note: There is always one and only one cell of type C (value 2) in a given grid.
Output:
Output should contain 2 lines for each test case.
1st line: Case#
2nd line: Count1 Count2
Where:
Count1: time in seconds when special empty cell (type C) will get filled.
Count2: time in seconds when whole grid will get filled with water (note: stone cell cannot be filled with acid).
Note:
1. Count2 will be -1if all cells of the grid (except stone cells) cannot be dissolved. Whole grid dissolving term means that all cells except stone get filled with Acid.
2. Count1 will be -1if empty cell cannot be filled. If empty cell cannot be filled the #1 is also applicable, i.e. then Count2 = -1.
3. Once acid enters special cell, it accumulates there for 1 second. After that the acid starts leaking to neighboring (left, right, up, down) cells.
4. The terms “dissolve”, “melt”, “leaking” are used to express similar meaning that the cell starts leaking the acid to its neighbor cells (left, right, up, down).
5. Acid is poured continuously so once a cell starts leaking acid, it may spread further to other cells in further course of time.
6. The maximum number of rows or columns of grid is 3000.
Sample Input:
9 ---->Number of test cases.
4 5 -------> N=4: number of rows, M= 5: number of columns
2 4 -----> Location of cell(row col) where acid is poured
1 0 1 0 1 ------> Grid 1st row with M cell entries
1 0 1 1 1 ----> Acid is poured on 4thcell of this (2nd) row.
1 1 2 1 1 -----> Rows contains empty cell (type C: value: 2)
1 0 1 0 1 -------> Last row of the grid with cell M values
3 3 ------> 2ndtest case starts, N=3, M=3
1 2 ---> Acid is pouring location
1 1 0 ---> 1strow of grid; Acid poured on 2nd cell of this (1st) row of the grid.
1 2 1
0 1 1
3 3
1 1
1 1 1
1 2 1
0 1 1
3 3
3 3
1 1 1
1 2 1
0 1 1
4 4
2 3
0 0 1 0
0 1 1 1
1 1 2 1
1 0 1 1
3 3
1 3
0 1 1
1 2 1
1 1 1
4 5
1 3
1 0 1 0 1
1 0 1 1 1
1 1 1 2 1
1 0 0 1 1
4 5
3 5
1 0 1 0 1
1 0 1 1 1
1 1 1 2 1
1 0 0 1 1
4 5
2 4
1 0 1 0 1
1 1 1 1 1
1 1 2 1 1
1 0 1 1 1
Sample Output:
Case #1
-1 -1 --->Count1 Count2 (refer to output description)
Case #2
-1 -1
Case #3
6 6
Case #4
6 6
Case #5
5 5
Case #6
6 6
Case #7
7 7
Case #8
5 9
Case #9
4 6
#include<iostream>
#define MAX_SIZE 9000000
#define SIZE_OF_ARR 3000
using namespace std;
int n, m, xStart, yStart, xEnd, yEnd;
int arr[SIZE_OF_ARR][SIZE_OF_ARR];
int visited[SIZE_OF_ARR][SIZE_OF_ARR];
int d[SIZE_OF_ARR][SIZE_OF_ARR];
int dem, dem_inque;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int rear = -1;
int front = -1;
int queX[MAX_SIZE];
int queY[MAX_SIZE];
bool isEmpty(){
return rear == front;
}
void push(int x, int y){
rear++;
queX[rear] = x;
queY[rear] = y;
}
void pop(){
front++;
}
int second;
void bfs(int x, int y){
rear = -1;
front = -1;
push(x, y);
visited[x][y] = 1;
while(!isEmpty()){
pop();
int tempX = queX[front];
int tempY = queY[front];
for(int h = 0; h < 4; h++){
int r = tempX + dx[h];
int c = tempY + dy[h];
if(r >0 && r <= n && c > 0 && c <= m && visited[r][c] == 0){
if(arr[r][c] == 1){
visited[r][c] = 1;
d[r][c] = d[tempX][tempY] + 1;
push(r, c);
if(d[r][c] > second) second = d[r][c];
dem_inque++;
}
}
}
}
}
void reset(){
for(int i = 1; i <= n; i++){
for(int j = 1; j<= m; j++){
visited[i][j] = 0;
d[i][j] = 0;
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
cout << "Case #" << tc << endl;
cin >> n >> m >> xStart >> yStart;
dem = 0;
reset();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> arr[i][j];
if(arr[i][j] == 2){
visited[i][j] = 1;
xEnd = i;
yEnd = j;
}
if(arr[i][j] == 0) visited[i][j] = 1;
if(arr[i][j] == 1) dem++;
}
}
second = 0;
dem_inque = 0;
bfs(xStart, yStart);
int maxx = 0;
bool flag = true;
for(int h = 0; h < 4; h++){
int tempR = xEnd + dx[h];
int tempC = yEnd + dy[h];
if(tempR > 0 && tempR <= n && tempC > 0 && tempC <= m){
if(d[tempR][tempC] > maxx) maxx = d[tempR][tempC];
if(visited[tempR][tempC] == 0){
flag = false;
break;
}
}
else{
flag = false;
break;
}
}
if(!flag) cout << -1 << " " << -1 << endl;
else if(dem_inque+1 != dem) cout << maxx+1 << " " << -1 << endl;
else cout << maxx + 1<< " " << second+1 << endl;
}
return 0;
}Editor is loading...