Thong tri khu vuc
quoc14
c_cpp
18 days ago
6.5 kB
3
Indexable
Never
DFS and BFS
Level 4 Thống trị khu vực Cho ma trận NxN (5 ≤ N ≤ 100) chứa các phần tử có giá trị 0 – 5 mô tả lãnh thổ 6 vương quốc. Yêu cầu sáp nhập các vùng số 0 về các lãnh thổ khác sao cho vùng đồng nhất có diện tích lớn nhất (các vùng được chuyển đổi trước không được tính vào diện tích để quyết định các vùng chuyển đổi sau), sau đó trả về số lượng vùng còn lại sau khi sáp nhập. Thông thường, chúng ta có thể thấy rõ rằng có hai ô 5, hai ô 4, một ô 3 và hai ô 2 gian hàng xung quanh ba ô 0 này. Tuy nhiên, vì ô 5 cũng kết nối với ô khác cùng loại (ô 5, tại vị trí [1,1] và [4,1] với màu xanh lam), diện tích sẽ trở lên tốt hơn, vì vậy chúng tôi coi tần suất của ô 5 là 4. Trong trường hợp có nhiều hơn một loại ô có cùng tần suất cao nhất, chúng tôi sẽ chọn ô có giá trị cao hơn. Tiếp tục với ô 0 tiếp theo ta có ma trận bên dưới Tất cả các Ô cùng loại và cạnh nhau (trên / dưới/ trái / phải) kết nối thành một khu vực. Ở ví dụ này chúng ta có 11 vùng [Input] - Số lượng test case T (T <= 50) - Kích thước ma trận N (5 <= N <= 100) - Chi tiết ma trận được cho trong N hàng tiếp theo, Giá trị của mỗi ô có giá trị C (0 <= C <= 5) 5 5 5 5 1 4 4 4 0 2 4 2 5 0 0 2 0 5 4 3 0 1 1 3 3 2 1 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 5 0 5 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 3 5 1 4 0 0 4 2 1 1 1 2 1 1 0 5 0 2 1 5 0 2 0 4 4 4 0 1 1 0 2 2 4 0 5 4 2 1 3 1 1 2 2 2 3 3 2 1 1 5 1 1 2 0 3 3 2 2 1 3 1 1 1 0 0 1 2 2 5 3 1 4 1 2 0 4 0 0 5 4 0 3 3 1 3 3 0 0 1 5 0 3 1 4 3 3 1 2 3 ... [Output] - Xuất ra số lượng vùng sau khi đổi các vùng số 0 Case #1 11 Case #2 1 Case #3 31 ... [Constraint] - Tất cả các ô số 0 cạnh nhau (trên/dưới/trái/phải) được tính là 1 khu vực. - Chỉ có 6 loại ô từ : 0 - 5, ô sô 0 cần được thay đổi thành các số khác từ (1-5) - Chúng tôi đảm bảo sẽ không có trường hợp nào trong đó tất cả các ô bằng không - Tất cả các loại ô giống nhau nằm xung quanh nhau được coi là một khu vực. - Time limit : 3s for 50 TC ( C, C++ 3000 msec, Java 6000 msec) Case #1 11 Case #2 1 Case #3 31 Case #4 130 Case #5 60 Case #6 44 Case #7 51 Case #8 51 Case #9 47 Case #10 1231 Case #11 1205 Case #12 1224 Case #13 1226 Case #14 1204 Case #15 1234 Case #16 1256 Case #17 1207 Case #18 1227 Case #19 1201 Case #20 1199 Case #21 1176 Case #22 1205 Case #23 1218 Case #24 1215 Case #25 1207 Case #26 1180 Case #27 1159 Case #28 1175 Case #29 1177 Case #30 3129 Case #31 4849 Case #32 4740 Case #33 4721 Case #34 4713 Case #35 4838 Case #36 4792 Case #37 4675 Case #38 4702 Case #39 4778 Case #40 4833 Case #41 4774 Case #42 4778 Case #43 4785 Case #44 4828 Case #45 4764 Case #46 4776 Case #47 4763 Case #48 4724 Case #49 4836 Case #50 4723 Time: 2.18600 s. #include <iostream> #include <time.h> using namespace std; int oo = 2000000000; int T, n, result; int mp[101][101], vs[101][101], arr[101][101]; // up down left right int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int q[10001][3], head, tail; int q1[10001][3], head1, tail1; void resetVs(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) vs[i][j] = 0; } } void init(){ head = 0, tail = 0; } void push(int x, int y, int p){ q[tail][0] = x, q[tail][1] = y, q[tail++][2] = p; } void pop(){ head++; } bool isEmpty(){ return head == tail; } int getX() {return q[head][0];} int getY() {return q[head][1];} int getC() {return q[head][2];} bool inSide(int x, int y){ return x >= 0 && x < n && y >= 0 && y < n; } int countBfs(int X, int Y, int cnt){ head1 = 0, tail1 = 0; vs[X][Y]++; q1[tail1][0] = X, q1[tail1][1] = Y, q1[tail1++][2] = cnt; while(head1 != tail1){ int x = q1[head1][0]; int y = q1[head1][1]; int c = q1[head1][2]; head1++; for(int d = 0; d < 4; d++){ int xx = x + dx[d]; int yy = y + dy[d]; if(inSide(xx, yy) && !vs[xx][yy] && mp[xx][yy] == mp[x][y]){ vs[xx][yy]++; q1[tail1][0] = xx, q1[tail1][1] = yy, q1[tail1++][2] = c+1; } } } return tail1; } void bfs(int X, int Y, int cnt, bool isFill){ init(); if(isFill) resetVs(); vs[X][Y]++; push(X, Y, cnt); int count[6] = {0, 0, 0, 0, 0, 0}; while(!isEmpty()){ int x = getX(); int y = getY(); int c = getC(); pop(); for(int d = 0; d < 4; d++){ int xx = x + dx[d]; int yy = y + dy[d]; if(inSide(xx, yy) && !vs[xx][yy]){ if(isFill && mp[xx][yy] == 0){ vs[xx][yy]++; push(xx, yy, -1); } else if(isFill && mp[xx][yy] > 0 && mp[xx][yy] < 6){ count[mp[xx][yy]] += countBfs(xx, yy, 1); } else if (!isFill && (mp[xx][yy] == mp[x][y] || mp[xx][yy] == -mp[x][y])){ vs[xx][yy]++; push(xx, yy, -1); } } } } if(isFill){ int index = 1, maxx = count[1]; for(int i = 2; i <= 5; i++){ if(count[i] >= maxx) maxx = count[i], index = i; } for(int i = 0; i < tail; i++) mp[q[i][0]][q[i][1]] = -index; }else result++; } 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 cin >> n; result = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ vs[i][j] = 0; cin >> mp[i][j]; } } // Solve Problem // fill for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(mp[i][j] == 0 && !vs[i][j]) bfs(i, j, -1, true); } } // count result resetVs(); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(!vs[i][j]) bfs(i, j, -1, false); } } // Output cout << "Case #" << tc << endl << result << 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