Untitled

 avatar
unknown
plain_text
2 years ago
2.9 kB
6
Indexable
#include<iostream>
using namespace std;
#define max1 110
#define max2 10000
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n;
int arr_map[max1][max1];
int arr_temp[max1][max1];
int dem;
int check[max1][max1];
int qx[max2];
int qy[max2], ff=0, rr=0;
void BFS_kq(int vt_hang,int vt_cot)
{
	ff=0, rr=0;
	qx[rr] = vt_hang;
	qy[rr] = vt_cot;
	rr++;
	check[vt_hang][vt_cot] = 1;
	int vung = arr_temp[vt_hang][vt_cot];
	while ( ff != rr)
	{
		int x2 = qx[ff];
		int y2 = qy[ff];
		ff++;
		for (int i = 0; i < 4; i++)
		{
			int hang = x2 + dx[i];
			int cot = y2 + dy[i];
			if(hang>=0 && hang<n && cot>=0 && cot<n && check[hang][cot] == 0)
			{
				if(vung == arr_temp[hang][cot])
				{
					check[hang][cot] = 1;
					qx[rr] = hang;
					qy[rr] = cot;
					rr++;
				}
			}
		}
	}
}
void BFS(int vt_hang,int vt_cot)
{
	ff=0, rr=0;
	int Luu_0x[max1];
	int Luu_0y[max1];
	Luu_0x[0] = vt_hang;
	Luu_0y[0] = vt_cot;
	int leng = 1;
	int dem[6]={0};
	int check_BFS[max1][max1]={0};
	qx[rr] = vt_hang;
	qy[rr] = vt_cot;
	rr++;
	check_BFS[vt_hang][vt_cot] = 1;
	while (ff != rr)
	{
		int x2 = qx[ff];
		int y2 = qy[ff];
		ff++;
		for (int i = 0; i < 4; i++)
		{
			int hang = x2 + dx[i];
			int cot = y2 + dy[i];
			if(hang>=0 && hang<n && cot >=0 && cot<n && check_BFS[hang][cot] == 0)
			{
				if(arr_map[x2][y2] == 0)
				{
					if(arr_map[hang][cot] == 0)
					{
						check_BFS[hang][cot] = 1;
						Luu_0x[leng] = hang;
						Luu_0y[leng] = cot;
						leng++;
						qx[rr] = hang;
						qy[rr] = cot;
						rr++;
					}
					else
					{
						check_BFS[hang][cot] = 1;
						dem[arr_map[hang][cot]]++;
						qx[rr] = hang;
						qy[rr] = cot;
						rr++;
					}
				}
				else
				{
					if(arr_map[x2][y2] == arr_map[hang][cot])
					{
						check_BFS[hang][cot] = 1;
						dem[arr_map[hang][cot]]++;
						qx[rr] = hang;
						qy[rr] = cot;
						rr++;
					}
				}
			}
		}
	}
	int max=0;
	int index = 0;
	for (int i = 0; i < 6; i++)
	{
		if(dem[i] >= max)
		{
			max = dem[i];
			index = i;
		}
	}
	for (int i = 0; i < leng; i++)
	{
		//arr_map[Luu_0x[i]][Luu_0y[i]] = -1;
		arr_temp[Luu_0x[i]][Luu_0y[i]] = index;
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	int th;cin>>th;
	for (int tc = 1; tc <= th; tc++)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> arr_map[i][j];
				arr_temp[i][j] = arr_map[i][j];
				check[i][j] = 0;
			}
		}///////////
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if(arr_map[i][j] == 0)
				{
					BFS(i,j);
				}
			}
		}///////////////
		dem = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if(check[i][j] == 0)
				{
					dem++;
					BFS_kq(i,j);
				}
			}
		}
		cout << "Case #" << tc << endl << dem << endl;
	}
	return 0;
}
Editor is loading...