Untitled
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...