Grid Axit
quoc14
c_cpp
5 months ago
8.9 kB
3
Indexable
DFS and BFS
Level 4
Grid Acid
Một lưới hình chữ nhật có kích thước N x M. Mỗi ô được làm bằng kim loại đặc biệt (loại A) hoặc bằng đá (loại B).
Nếu đổ axit vào một ô lưới, axit có thể làm tan chảy ô lưới (đối với loại A: ô lưới kim loại đặc biệt) và lan rộng hơn hoặc không đi qua ô lưới (đối với loại B: ô lưới đá).
Pin được làm bằng kim loại đặc biệt (loại A) có thể tan chảy trong axit trong 1 giây và do đó cho phép axit lan rộng hơn.
Bình làm bằng đá (loại B) không phản ứng với axit và do đó không nóng chảy hoặc không cho axit đi qua.
Có một loại tế bào thứ ba là tế bào rỗng (loại C), nhưng có ranh giới (cả 4 mặt) được phủ bằng kim loại bảo vệ.
Hình. Một lưới có kích thước 7 x 8 làm ví dụ
Nếu cả 4 mặt của nó (loại C: ô rỗng) tiếp xúc với axit tại bất kỳ thời điểm nào, thì trong trường hợp đó, ranh giới của nó (cả 4 mặt) sẽ tan chảy và cho phép axit đi qua. Trong trường hợp đó, nó (loại C: ô rỗng) sẽ được lấp đầy bằng axit.
Chỉ có một và chỉ một ô như vậy trong một lưới nhất định.
Axit được đổ vào một ô lưới, ô lưới này được làm bằng kim loại đặc biệt có thể tan chảy trong axit.
Đảm bảo rằng axit sẽ chỉ được đổ vào một ô được làm bằng kim loại đặc biệt (loại A), không phải vào đá (loại B) hoặc ô rỗng (loại C).
Axit được đổ liên tục cho đến khi tất cả các ô lưới (trừ đá - loại B) tan chảy hoàn toàn.
Bạn phải biết khi nào ô trống có ranh giới bảo vệ đặc biệt sẽ được lấp đầy axit và khi nào toàn bộ lưới sẽ được lấp đầy axit (trừ các ô được tạo thành từ đá).
Phải mất 1 giây để axit hòa tan một tế bào kim loại đặc biệt và sau đó nó có thể lan sang 4 tế bào lân cận trực giao (Trái, Phải, Trên, Dưới).
Đầu vào:
Mục nhập đầu tiên là số lượng trường hợp thử nghiệm; phần còn lại là đầu vào của từng trường hợp thử nghiệm.
Đối với mỗi trường hợp thử nghiệm, hàng đầu tiên chứa N và M là hai số nguyên được phân tách bằng một khoảng trắng.
Hàng tiếp theo chứa vị trí của ô (số hàng và cột được phân cách bằng dấu cách) nơi axit sẽ được đổ liên tục cho đến khi toàn bộ lưới (trừ các ô đá) tan chảy.
N hàng tiếp theo chứa M giá trị số nguyên, mỗi giá trị chứa loại ô.
Giá trị loại ô có 3 loại:
- 0 : tế bào là đá (loại B)
- 1: pin được làm bằng kim loại đặc biệt (loại A)
- 2: ô là ô rỗng đặc biệt, có ranh giới đặc biệt (loại C)
Lưu ý: Luôn có một và chỉ một ô loại C (giá trị 2) trong một lưới nhất định.
Đầu ra:
Đầu ra phải chứa 2 dòng cho mỗi trường hợp thử nghiệm.
Dòng 1: Trường hợp số
Dòng thứ 2: Đếm 1 Đếm 2
Ở đâu:
Count1: thời gian tính bằng giây khi ô trống đặc biệt (loại C) được lấp đầy.
Count2: thời gian tính bằng giây khi toàn bộ lưới sẽ được đổ đầy nước (lưu ý: không thể đổ đầy axit vào ô đá).
Ghi chú:
1. Count2 sẽ là -1 nếu tất cả các ô của lưới (trừ các ô đá) không thể hòa tan. Thuật ngữ hòa tan toàn bộ lưới có nghĩa là tất cả các ô trừ đá đều được lấp đầy bằng Axit.
2. Count1 sẽ là -1 nếu ô trống không thể điền đầy. Nếu ô trống không thể điền đầy thì #1 cũng áp dụng được, tức là Count2 = -1.
3. Khi axit đi vào tế bào đặc biệt, nó sẽ tích tụ ở đó trong 1 giây. Sau đó, axit bắt đầu rò rỉ sang các tế bào lân cận (trái, phải, trên, dưới).
4. Các thuật ngữ “hòa tan”, “tan chảy”, “rò rỉ” được sử dụng để diễn tả ý nghĩa tương tự rằng tế bào bắt đầu rò rỉ axit sang các tế bào lân cận (trái, phải, trên, dưới).
5. Axit được đổ liên tục nên khi một tế bào bắt đầu rò rỉ axit, axit có thể lan sang các tế bào khác theo thời gian.
6. Số hàng hoặc cột tối đa của lưới là 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
Case #1
-1 -1
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
5 5
Case #10
4 4
Case #11
6 6
Case #12
10 16
Case #13
-1 -1
Case #14
-1 -1
Case #15
-1 -1
Case #16
-1 -1
Case #17
8 9
Case #18
-1 -1
Case #19
-1 -1
Case #20
-1 -1
Case #21
12 12
Case #22
21 -1
Case #23
62 -1
Case #24
92 -1
Case #25
-1 -1
Case #26
195 -1
Case #27
199 -1
Case #28
-1 -1
Case #29
999 1001
Case #30
-1 -1
Time: 7.09900 s.
#include <iostream>
#include <time.h>
using namespace std;
int oo = 2000000000;
int T, n, m ,sr, sc, X, Y, ans1, ans2, cnt;
int mp[3000][3000], vs[3000][3000];
// up down left right
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int q[9000000][2], head, tail;
bool inSize(int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
}
int checkC(){
int maxx = -oo, count = 0;
for(int d = 0; d < 4; d++){
int xx = X + dx[d];
int yy = Y + dy[d];
if(!inSize(xx, yy)) return oo;
else if(inSize(xx, yy)){
if(vs[xx][yy] == oo) return oo + 1;
else if(vs[xx][yy] > 0){
count++;
if(vs[xx][yy] > maxx) maxx = vs[xx][yy];
}
}
}
return (count == 4 ? maxx : oo);
}
void bfs(){
// init
head = 0, tail = 0;
// push
vs[sr][sc]++;
q[tail][0] = sr, q[tail++][1] = sc;
while(head != tail){
// get value
int x = q[head][0];
int y = q[head][1];
cnt++;
// pop
head++;
if(vs[x][y] > ans2) ans2 = vs[x][y];
if(vs[X][Y] == oo){
int c = checkC();
if(c != oo){
ans1 = c;
vs[X][Y] = c;
q[tail][0] = X, q[tail++][1] = Y;
}
}
for(int d = 0; d < 4; d++){
int xx = x + dx[d];
int yy = y + dy[d];
if(inSize(xx, yy) && !vs[xx][yy]){
if(mp[xx][yy] == 1){
// push
vs[xx][yy] = vs[x][y]+1;
q[tail][0] = xx, q[tail++][1] = yy;
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
// Calc clock
clock_t time_start, time_end;
time_start = clock();
cin >> T;
for(int tc = 1; tc <= T; tc++){
// Initial && Input
ans1 = oo, ans2 = -oo, cnt = 0;
cin >> n >> m;
cin >> sr >> sc;
sr--, sc--;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
vs[i][j] = 0;
cin >> mp[i][j];
if(mp[i][j] == 2) X = i, Y = j, vs[X][Y] = oo;
else if(mp[i][j] == 0) vs[i][j] = oo, cnt++;
}
}
// Solve Problem
if(checkC() > oo){
ans1 = -1, ans2 = -1;
} else{
bfs();
if(ans1 == oo) ans1 = -1;
if(ans1 == -1 || cnt != n*m) ans2 = -1;
}
// Output
cout << "Case #" << tc << endl << ans1 << " " << ans2 << endl;
}
// Calc Time
time_end = clock();
cout.setf(ios::fixed);
cout.precision(5);
cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
return 0;
}Leave a Comment