Thong tri khu vuc

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;
 }