Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.1 kB
11
Indexable
Never
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.

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

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.

5

5

1

4

4

4

5

2

4

2

5

5

5

2

0

5

4

3

0

1

1

3

3

2

1

Tiếp tục với ô 0 tiếp theo ta có ma trận bên dưới

5

5

1

4

4

4

5

2

4

2

5

5

5

2

2

5

4

3

3

1

1

3

3

2

1

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.

5

5

1

4

4

4

5

2

4

2

5

5

5

2

2

5

4

3

3

1

1

3

3

2

1

Ở 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

...
/////////////////////////////////////////
#include<iostream>
using namespace std;
int N;
int A[105][105];
int visit[105][105];
int A_copy[105][105];
int vuongquoc[6];
int f=-1, r=-1;
int Qx[100000];
int Qy[100000];
int dx[4]= {1,-1,0,0};
int dy[4]={0,0,1,-1};
void push(int x, int y)
{
	f++;
	Qx[f] =x;
	Qy[f] =y;
}
void pop(int &x, int &y)
{
	r++;
	x= Qx[r];
	y=Qy[r];
}
void reset()
{
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			visit[i][j] =0;
		}
	}
	for(int i=0; i<6; i++)
	{
		vuongquoc[i] =0;
	}
}

void bfs_vung(int x,int y)
{
	push(x,y);
	visit[x][y] =1;
	while(f != r)
	{
		pop(x,y);
		for(int i=0; i<4; i++)
		{
			int xx= x+dx[i];
			int yy= y+dy[i];
			if(xx >=1 && xx <=N && yy>=1 && yy<=N && visit[xx][yy] ==0 && A_copy[xx][yy] == A_copy[x][y]){
				push(xx,yy);
				visit[xx][yy]=1;
			}
		}
	}
}

void bfs(int x,int y)
{
	push(x,y);
	visit[x][y] =1;
	while(f != r)
	{
		pop(x,y);
		for(int i=0; i<4; i++)
		{
			int xx= x+dx[i];
			int yy= y+dy[i];
			if(xx >=1 && xx <=N && yy>=1 && yy<=N && visit[xx][yy] ==0 ){
				if((A[x][y] ==0 ) || (A[x][y] != 0 && A[xx][yy] == A[x][y])){
					push(xx,yy);
					//cout << xx << " " << yy << endl;
					vuongquoc[A[xx][yy]] ++;
					visit[xx][yy] =1;
				}
			}
		}
	}

}
int main()
{
	//freopen("Text.txt","r",stdin);
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt++)
	{
		cin >>N;
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				cin >> A[i][j];
				A_copy[i][j] = A[i][j];
			}
		}
		/////////////////////
		for(int i=1; i<= N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				/////////////////////////
				if(A_copy[i][j] ==0 ){
					//cout << " hi" << i << " " << j << endl;
					reset();
					bfs(i,j);
					int maxx=0;
					int a=0;
					for(int i=5; i>0; i--){
						if(vuongquoc[i] > maxx){ maxx= vuongquoc[i]; a=i; }
						//cout << a << endl;
					}
					///////////
					for(int row=1; row <=N; row ++)
					{
						for(int col=1; col <=N; col ++)
						{
							if(visit[row][col] ==1 && A[row][col] == 0){
								A_copy[row][col]=a;
							}
						}
					}
				}
				///////////////////////////////////////
			}
		
		}
		
		int count_ =0;
		reset();
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				if(visit[i][j] == 0)
				{
					bfs_vung(i,j);
					count_ ++;
				}			
			}
		}
		cout << "Case "<< stt << endl << count_ << endl;
	}
	return 0;
}