Untitled

mail@pastecode.io avatar
unknown
plain_text
15 days ago
3.4 kB
2
Indexable
Never
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, map[20][20], re_map[20][20];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int visit[20][20];
int step;
queue<pair<int, int>> q;
unordered_map<int, vector<int>> hash_hozion, hash_vertical;

void init(int N, int mMap[20][20]) {
	n = N;
	step = 0;
	int sum0deg = 0, sum90deg=0, sum180deg=0, sum270deg=0;
	hash_hozion.clear();
	hash_vertical.clear();
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			re_map[i][j] = map[i][j] = mMap[i][j];
			visit[i][j] = 0;
			for(int k=1; k<5; k++) {
				if(j + k < N) {
					sum0deg = sum0deg * 10 + map[i][j+k] - map[i][j+k-1] + 5;
					if(hash_hozion.find(sum0deg) == hash_hozion.end()) {
						hash_hozion[sum0deg].push_back(i*n+j);
					} 

					sum180deg = sum180deg * 10 + map[i][j+k-1] - map[i][j+k] + 5;
					if(hash_hozion.find(sum180deg) == hash_hozion.end()) {
						hash_hozion[sum180deg].push_back(i*n+j);
					} 
				}
				if(i + k < N) {
					sum90deg = sum90deg * 10 + map[i+k][j] - map[i+k-1][j] + 5;
					if(hash_vertical.find(sum90deg) == hash_vertical.end()) {
						hash_vertical[sum90deg].push_back(j*n+i);
					} 
					sum270deg = sum270deg * 10 + map[i+k-1][j] - map[i+k][j]  +5;
					if(hash_vertical.find(sum270deg) == hash_vertical.end()) {
						hash_vertical[sum270deg].push_back(j*n+i);
					} 
				}
			}
		}
	}		
}

int numberOfCandidate(int M, int mStructure[5]) {
	if(M == 1) return n*n;
	int key = 0;
	for(int i=0; i<M-1; i++) {
		key = key * 10 + mStructure[i] - mStructure[i+1] + 5;
	}
	return hash_hozion[key].size() + hash_vertical[key].size();
}
int bfs( int mSeaLevel) {
	//step++;
	int cnt = n*n;
	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) {
				cnt--;
				visit[i][j] = 1;
				q.push(make_pair(i, j));
			}
		}
	}
	while(!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		for(int k=0; k<4; k++) {
			int row = r + dx[k];
			int col = c + dy[k];
			if(row >=0 && row < n && col >=0 && col < n && !visit[row][col] && map[row][col]< mSeaLevel) {
				q.push(make_pair(row,col));
				cnt--;
				visit[row][col] = 1;
			}
		}
	}
	return cnt;
}
int maxArea(int M, int mStructure[5], int mSeaLevel) {
	int ans = -1;
	if(M == 1) {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				map[i][j] += mStructure[0];
				int temp = bfs(mSeaLevel);
				map[i][j] -= mStructure[0];
				ans = temp > ans ? temp : ans;
			}
		}
	}
	int key = 0;
	for(int i=0; i<M-1; i++) {
		key = key * 10 + mStructure[i] - mStructure[i+1] + 5;
	}
	if(!hash_hozion[key].empty()) {
		for(auto it:hash_hozion[key]) {
			int row = it / n;
			int col = it % n;

			for(int i=0; i<M; i++) {
				map[row][col+i] += mStructure[i];
			}

			int temp = bfs(mSeaLevel);
			ans = temp > ans ? temp : ans;

			for(int i=0; i<M; i++) {
				map[row][col+i] -= mStructure[i];
			}
		}
	}
	if(!hash_vertical[key].empty()) {
		for(auto it:hash_vertical[key]) {
			int row = it / n;
			int col = it % n;

			for(int i=0; i<M; i++) {
				map[row+i][col] += mStructure[i];
			}

			int temp = bfs(mSeaLevel);
			ans = temp > ans ? temp : ans;

			for(int i=0; i<M; i++) {
				map[row+i][col] -= mStructure[i];
			}
		}
	}
	return ans;
}
Leave a Comment