Untitled
#include <iostream> #define MAX_Q 40000 using namespace std; int board[105][105]; int saveboad[105][105]; int mark[105][105]; int tmpboard[105][105]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int N,ans; typedef struct { int x; int y; } Node; class Queue { private: int front; int rear; Node arr[MAX_Q]; public: Queue() { front = -1; rear = -1; } bool isFull() { return (rear == MAX_Q - 1); } int size(){ return rear; } bool isEmpty() { return (front == -1 && rear == -1); } void enqueue(Node x) { if (isFull()) { return; } if (isEmpty()) { front = 0; rear = 0; } else { rear++; } arr[rear] = x; } void dequeue() { if (isEmpty()) { return; } if (front == rear) { front = -1; rear = -1; } else { front++; } } Node peek() { if (isEmpty()) { return Node(); } return arr[front]; } }; void bfs(Node a){ Queue q; int sum[6] = {0,0,0,0,0,0}; q.enqueue(a); Node save0[MAX_Q]; mark[a.x][a.y] = true; int k = 0; while (!q.isEmpty()) { Node oldNode = q.peek(); q.dequeue(); if (board[oldNode.x][oldNode.y] == 0) { k++; save0[k] = oldNode; } if (board[oldNode.x][oldNode.y] == 0) { for (int i = 0; i < 4; i++) { Node nextNode; nextNode.x = oldNode.x + dx[i]; nextNode.y = oldNode.y + dy[i]; if (nextNode.x > N || nextNode.x <1 ) continue; if (nextNode.y > N || nextNode.y <1 ) continue; if (!mark[nextNode.x][nextNode.y]) { mark[nextNode.x][nextNode.y] = true; sum[board[nextNode.x][nextNode.y]]++; q.enqueue(nextNode); } } } if (board[oldNode.x][oldNode.y] != 0 ) { for (int i = 0; i < 4; i++) { Node nextNode; nextNode.x = oldNode.x + dx[i]; nextNode.y = oldNode.y + dy[i]; if (nextNode.x > N || nextNode.x < 1 ) continue; if (nextNode.y > N || nextNode.y < 1 ) continue; if (!mark[nextNode.x][nextNode.y] && board[nextNode.x][nextNode.y] == board[oldNode.x][oldNode.y]) { mark[nextNode.x][nextNode.y] = true; sum[board[nextNode.x][nextNode.y]]++; q.enqueue(nextNode); } } } } int maxsum = 0; int t; for (int i = 5; i > 0; i--) { if (sum[i] > maxsum) { maxsum = sum[i]; t = i; } } for (int i = 1; i <= k; i++) { saveboad[save0[i].x][save0[i].y] = t; } } void bfsvung(Node dau){ Queue q; q.enqueue(dau); mark[dau.x][dau.y]=1; while (!q.isEmpty()) { Node oldNode = q.peek(); q.dequeue(); for (int i=0; i<4; i++){ Node nextNode; nextNode.x=oldNode.x+dx[i]; nextNode.y=oldNode.y+dy[i]; if (nextNode.x > N || nextNode.x <1 ) continue; if (nextNode.y > N || nextNode.y <1 ) continue; if (mark[nextNode.x][nextNode.y]==0 && saveboad[nextNode.x][nextNode.y]==saveboad[oldNode.x][oldNode.y]){ mark[nextNode.x][nextNode.y]=1; q.enqueue(nextNode); } } } }; void initvisit(){ for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ mark[i][j]=0; } } } int main(){ int T; //freopen("input.txt","r",stdin); cin >>T; for (int tc = 0; tc < T; tc++) { cin >>N; for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ cin >> board[i][j]; mark[i][j]=0; saveboad[i][j]=board[i][j]; } } for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ if (saveboad[i][j]==0){ Node p; p.x=i; p.y=j; bfs(p); initvisit(); } } } ans=0; for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ if (mark[i][j]==0){ ans++; Node pdau; pdau.x=i; pdau.y=j; bfsvung(pdau); } } } cout <<"Case #"<< tc + 1 << endl << ans << endl; } return 0; }
Leave a Comment