Untitled
unknown
plain_text
2 years ago
4.0 kB
3
Indexable
#include <iostream> using namespace std; #define MAX_SIZE 10000000 int front = -1; int rear = -1; int Arx[MAX_SIZE]; int Ary[MAX_SIZE]; class queue { public: bool isEmpty(); void push(int arx, int ary); void pop(); void peek(int &arx, int &ary); }; bool queue :: isEmpty() { if(front == rear) { return true; } return false; } void queue :: push(int arx, int ary) { front++; Arx[front] = arx; Ary[front] = ary; } void queue :: pop() { rear++; } void queue :: peek(int &arx, int &ary) { arx = Arx[rear + 1]; ary = Ary[rear + 1]; } int front1 = -1; int rear1 = -1; int Arx1[MAX_SIZE]; int Ary1[MAX_SIZE]; class queue1 { public: bool isEmpty(); void push(int arx, int ary); void pop(); void peek(int &arx, int &ary); }; bool queue1 :: isEmpty() { if(front1 == rear1) { return true; } return false; } void queue1 :: push(int arx, int ary) { front1++; Arx1[front1] = arx; Ary1[front1] = ary; } void queue1 :: pop() { rear1++; } void queue1 :: peek(int &arx, int &ary) { arx = Arx1[rear1 + 1]; ary = Ary1[rear1 + 1]; } int N; int arr[101][101]; int vs[101][101]; int visited[101][101]; int cnt[6]; int vtx[10001]; int vty[10001]; int id = 0; void reset(int ar[101][101]) { for(int i = 0; i < 101; i++) { for(int j = 0; j < 101; j++) { ar[i][j] = 0; } } for(int i = 0; i < 6; i++) { cnt[i] = 0; } for(int i = 0; i < 10001; i++) { vtx[i] = 0; vty[i] = 0; } id = 0; } int dx[] = { -1, 0, 0, 1}; int dy[] = { 0, 1, -1, 0}; void BFS1(queue1 qe1) { while(!qe1.isEmpty()) { int x, y; qe1.peek(x, y); qe1.pop(); cnt[arr[x][y]]++; for(int i = 0; i < 4; i++) { int t = x + dx[i]; int k = y + dy[i]; if(t >= 0 && t < N && k >= 0 && k < N) { if(vs[t][k] == 0 && arr[t][k] == arr[x][y]) { qe1.push(t, k); vs[t][k] = 1; } } } } } // BFS nhung phan tu 0 va xem nhung phan tu ke no void BFS(int x1, int y1) { queue qe; queue1 qe1; front1 = rear1 = -1; front = rear = -1; reset(vs); vs[x1][y1] = 1; qe.push(x1, y1); while (!qe.isEmpty()) { int x, y; qe.peek(x, y); qe.pop(); if(arr[x][y] == 0) { vtx[id] = x; vty[id] = y; id++; for(int i = 0; i < 4; i++) { int t = x + dx[i]; int k = y + dy[i]; if(t >= 0 && t < N && k >= 0 && k < N) { if(vs[t][k] == 0) { qe.push(t, k); vs[t][k] = 1; } } } } else { qe1.push(x, y); } } BFS1(qe1); int max = 0; int ii = 0; for(int i = 5; i >= 1; i--) { if(max < cnt[i]) { max = cnt[i]; ii = i; } } for(int i = 0; i < id; i++) { visited[vtx[i]][vty[i]] = ii; } } void BFS2(int x1, int y1, int k1) { queue qe; qe.push(x1, y1); vs[x1][y1] = 1; while(!qe.isEmpty()) { int x, y; qe.peek(x, y); qe.pop(); for(int i = 0; i < 4; i++) { int t = x + dx[i]; int k = y + dy[i]; if(t >= 0 && t < N && k >= 0 && k < N) { if(arr[t][k] == k1 && vs[t][k] == 0) { qe.push(t , k); vs[t][k] = 1; } } } } } int main() { int testcase; cin >> testcase; for(int tc = 1; tc <= testcase; tc++) { cin >> N; reset(arr); reset(visited); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { cin >> arr[i][j]; } } for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(arr[i][j] == 0 && visited[i][j] == 0) { BFS(i, j); } } } for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(visited[i][j] != 0) { arr[i][j] = visited[i][j]; } } } int ctt = 0; reset(vs); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(vs[i][j] == 0) { BFS2(i, j, arr[i][j]); ctt++; } } } cout<<"Case #"<<tc<<endl<<ctt<<endl; } }
Editor is loading...