Untitled
unknown
plain_text
25 days ago
4.8 kB
1
Indexable
Never
#include <iostream> using namespace std; int T, N; int arr[105][105]; class Queue{ int front, rear; int q[10000000]; public: Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); void resetFront(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } void Queue::reset(){ front = rear = -1; } bool Queue::is_Empty(){ return front == rear; } void Queue::resetFront(){ front = -1; } int check[105][105]; int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, 1, -1}; int cnt[6]; bool visited[105][105]; Queue rQueue, cQueue; Queue frQueue, fcQueue; int map[105][105]; int tmp[105][105]; int findMaxField(int x, int y){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ check[i][j] = 0; } } frQueue.reset(); fcQueue.reset(); check[x][y] = 1; int count = 1; frQueue.enQueue(x); fcQueue.enQueue(y); while(frQueue.is_Empty() == false){ int cr = frQueue.deQueue(); int cc = fcQueue.deQueue(); for(int i = 0; i < 4; i++){ int row = cr + X[i]; int col = cc + Y[i]; if(row >= 0 && row < N && col >= 0 && col < N && check[row][col] == 0 && tmp[row][col] == tmp[cr][cc]){ check[row][col] = 1; frQueue.enQueue(row); fcQueue.enQueue(col); count++; } } } return count; } void BFS(int x, int y){ rQueue.reset(); cQueue.reset(); visited[x][y] = true; rQueue.enQueue(x); cQueue.enQueue(y); while(rQueue.is_Empty() == false){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == false && arr[nr][nc] == 0){ visited[nr][nc] = true; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } for(int i = 0; i < 6; i++){ cnt[i] = 0; } for(int k = 5; k >= 1; k--){ rQueue.resetFront(); cQueue.resetFront(); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ tmp[i][j] = arr[i][j]; } } while(rQueue.is_Empty() == false){ int row = rQueue.deQueue(); int col = cQueue.deQueue(); tmp[row][col] = k; } cnt[k] = findMaxField(x, y); } int ans = 0; int index; for(int i = 0; i < 6; i++){ if(cnt[i] >= ans){ ans = cnt[i]; index = i; } } rQueue.resetFront(); cQueue.resetFront(); while(rQueue.is_Empty() == false){ int r = rQueue.deQueue(); int c = cQueue.deQueue(); map[r][c] = index; } } void demvung(int x, int y){ rQueue.reset(); cQueue.reset(); visited[x][y] = true; rQueue.enQueue(x); cQueue.enQueue(y); while(rQueue.is_Empty() == false){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == false && map[nr][nc] == map[cr][cc]){ visited[nr][nc] = true; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } } int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> arr[i][j]; visited[i][j] = false; } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(visited[i][j] == false && arr[i][j] == 0){ BFS(i, j); } } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ visited[i][j] = false; if(arr[i][j] != 0){ map[i][j] = arr[i][j]; } } } int res = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(visited[i][j] == false){ res++; demvung(i, j); } } } cout << "Case #" << tc << endl; cout << res << endl; } return 0; }
Leave a Comment