Untitled

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <queue>
using namespace std;

int n, map[20][20], re_map[20][20];
bool visited[20][20]; 
vector<int> v;
vector<int> re_v;
int isInstall;
int temp;
void init(int N, int mMap[20][20])
{
	isInstall = 0;
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout<<mMap[i][j]<<" ";
			re_map[i][j] = map[i][j] = mMap[i][j];
			visited[i][j] = false;
		}
		cout<<endl;
	}
	cout<<"------------------"<<endl;
	v.clear();
	re_v.clear();
}


int numberOfCandidate(int M, int mStructure[5])
{
	if (M == 1) return n * n;
	int cnt = 0;
	unordered_map<string, bool> horizontal_cache, vertical_cache;


	for (int i = 0; i < M; i++) {
		v.push_back(mStructure[i]);
		re_v.push_back(mStructure[M - i - 1]);
	}

	//Check NxN island
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			// Check horizontal
			if (j + M <= n) {
				string pattern;
				for (int k = 0; k < M; k++) {
					pattern += to_string(map[i][j + k]) + ",";
				}
				if (horizontal_cache.find(pattern) == horizontal_cache.end()) {
					bool valid = true;
					for (int k = 0; k < M - 1; k++) {
						temp = map[i][j + k] + v[k];
						if (map[i][j + k] + v[k] != map[i][j + k + 1] + v[k + 1] &&
							map[i][j + k] + re_v[k] != map[i][j + k + 1] + re_v[k + 1]) {
								valid = false;
								break;
						}
					}
					horizontal_cache[pattern] = valid;
				}
				if (horizontal_cache[pattern]) {
					// Update value island
					if(isInstall) {
						for (int k = 0; k < M; k++) {
							map[i][j + k] = temp; 
						}
					}
					cnt++;
				}
			}

			// Check vertical
			if (i + M <= n) {
				string pattern;
				for (int k = 0; k < M; k++) {
					pattern += to_string(map[i + k][j]) + ",";
				}
				if (vertical_cache.find(pattern) == vertical_cache.end()) {
					bool valid = true;
					for (int k = 0; k < M - 1; k++) {
						temp = map[i + k][j] + v[k];
						if (map[i + k][j] + v[k] != map[i + k + 1][j] + v[k + 1] &&
							map[i + k][j] + re_v[k] != map[i + k + 1][j] + re_v[k + 1]) {
								valid = false;
								break;
						}
					}
					vertical_cache[pattern] = valid;
				}
				if (vertical_cache[pattern]) {
					// Update value island
					if(isInstall) {
						for (int k = 0; k < M; k++) {
							map[i + k][j] = temp;; 
						}
					}
					cnt++;
				}
			}
		}
	}

	return cnt;
}

//Check valid
bool isValid(int x, int y, int mSeaLevel) {
	return (x >= 0 && x < n && y >= 0 && y < n && map[x][y] < mSeaLevel && !visited[x][y]);
}

// BFS
void BFS(int x, int y, int mSeaLevel) {
	int dx[] = {-1, 1, 0, 0};
	int dy[] = {0, 0, -1, 1};
	queue<pair<int, int>> q;
	q.push(make_pair(x,y));
	visited[x][y] = true;

	while (!q.empty()) {
		pair<int, int> current = q.front();
		q.pop();

		int cx = current.first;
		int cy = current.second;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			if (isValid(nx, ny, mSeaLevel)) {
				map[nx][ny] = 0;
				visited[nx][ny] = true;
				q.push(make_pair(nx,ny));
			}
		}
	}
}


int maxArea(int M, int mStructure[5], int mSeaLevel)
{
	// Update map island
	isInstall = 1;
	int way_install = numberOfCandidate(M, mStructure);
	isInstall = 0;
	if(!way_install) return -1;
	// Count island 
	int island_count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(i==0 || i==n-1 || j==0 || j== n-1) {
				if (map[i][j] < mSeaLevel && !visited[i][j]) {
					BFS(i, j, mSeaLevel);
					
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(map[i][j] >= mSeaLevel) island_count++;
			/*map[i][j] = re_map[i][j];
			visited[i][j] = false;*/
			cout<<map[i][j]<<" ";
		}
		cout<<endl;
	}
	return island_count + 1;
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	cin >> n;
	int initial_map[20][20];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> initial_map[i][j];
		}
	}
	init(n, initial_map);
	int mstructure[3] = {5,2,3};
	cout <<maxArea(3, mstructure,6)  << endl;
	/*int mstructure4[1] = {4};
	cout<<numberofcandidate(1, mstructure4)<<endl;
	int mstructure2[5] = {1,5,1,3,5};
	cout << maxarea(3, mstructure2, 4)  << endl;
	int mstructure3[3] = {1,1,1};
	cout <<numberofcandidate(3, mstructure3)  << endl;*/
	return 0;
}