Untitled

[Nguyễn Quang Dũng] 08-28-2024 16:18
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct structures
{
	int r,c;
	int reverse;
};
int n;
structures str[10000];
unordered_map<int,vector<int>> Hash_hozirontal_Structures2Id;
unordered_map<int,vector<int>> Hash_vertical_Structures2Id;
int visit[21][21];
int map[21][21];
int num;
int stepvisit;
int coso[5]={0,1,10,100,1000};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
queue<pair<int,int>> q;
void add(int r,int c,int value,int rev,int dir)
{
	num++;
	str[num].r=r;
	str[num].c=c;
	str[num].reverse=rev;
	if(dir==0) Hash_hozirontal_Structures2Id[value].push_back(num);
	else Hash_vertical_Structures2Id[value].push_back(num);
}
void init(int N, int mMap[20][20])
{
	n=N;
	stepvisit=num=0;
	Hash_hozirontal_Structures2Id.clear();
	Hash_vertical_Structures2Id.clear();
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++) map[i][j]=mMap[i][j];
	for(int i=0;i<21;i++)
		for(int j=0;j<21;j++) visit[i][j]=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			int ngang[2] = {0, 0}, doc[2] = {0, 0};
            for(int k = 1; k < 5; k++) {
                if(j+k < N) {
                    ngang[0] = ngang[0] * 10 + (map[i][j+k] - map[i][j+k-1] + 5);
                    add(i, j, ngang[0], 0, 0);
 
                    ngang[1] = ngang[1] + (map[i][j+k-1] - map[i][j+k] + 5) * coso[k];
                    if(ngang[1] != ngang[0]) add(i, j, ngang[1], 1, 0);
                }
                if(i+k < N) {
                    doc[0] = doc[0] * 10 + (map[i+k][j] - map[i+k-1][j] + 5);
                    add(i, j, doc[0], 0, 1);
 
                    doc[1] = doc[1] + (map[i+k-1][j] - map[i+k][j] + 5) * coso[k];
                    if(doc[1] != doc[0]) add(i, j, doc[1], 1, 1);
                }
            }
		}
	}
}
				
int numberOfCandidate(int M, int mStructure[5])
{
	int key=0;
	if(M==1) return n*n;
	for(int i=1;i<M;i++)
	{
		key=key*10+(mStructure[i-1] - mStructure[i] + 5);
	}
	return Hash_hozirontal_Structures2Id[key].size()+Hash_vertical_Structures2Id[key].size();
}

[Nguyễn Quang Dũng] 08-28-2024 16:18
int bfs(int mSealevel)
{
	stepvisit++;
	int counter=n*n;
	for(int i=0;i<n;i++)
	{
		if(map[i][0]<mSealevel&&visit[n-1][i]<stepvisit)
		{
			counter--;
			visit[i][0]=stepvisit;
			q.push(make_pair(i,0));
		}
		if(map[i][n-1]<mSealevel&&visit[n-1][i]<stepvisit)
		{
			counter--;
			visit[i][n-1]=stepvisit;
			q.push(make_pair(i,n-1));
		}
	}
	for(int i=1;i<n-1;i++)
	{
		if(map[0][i]<mSealevel&&visit[0][i]<stepvisit)
		{
			counter--;
			visit[0][i]=stepvisit;
			q.push(make_pair(0,i));
		}
		if(map[n-1][i]<mSealevel&&visit[n-1][i]<stepvisit)
		{
			counter--;
			visit[n-1][i]=stepvisit;
			q.push(make_pair(n-1,i));
		}
	}
	while(!q.empty())
	{
		int r=q.front().first;
		int c=q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int row=r+dir[i][0];
			int col=c+dir[i][1];
			if(row>=0&&row<n&&col>=0&&col<n&&visit[row][col]<stepvisit&&map[row][col]<mSealevel)
			{
				q.push(make_pair(row,col));
				counter--;
				visit[row][col]=stepvisit;
			}
		}
	}
	return counter;
}
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];
				if(temp>ans) ans=temp;
			}
		}
		return ans;
	}
	int key=0;
	for(int i=1;i<M;i++)
	{
		key=key*10+(mStructure[i-1] - mStructure[i] + 5);
	}
	if(!Hash_hozirontal_Structures2Id[key].empty())
	{
		for(int itr:Hash_hozirontal_Structures2Id[key])
		{
			int row = str[itr].r, col = str[itr].c;
			if(str[itr].reverse==0)
			{
				for(int i=0;i<M;i++)
				{
					map[row][col+i]+=mStructure[i];
				}
				int temp=bfs(mSeaLevel);
				if(temp>ans) ans=temp;
				for(int i=0;i<M;i++)
				{
					map[row][col+i]-=mStructure[i];
				}
			}
			else if(str[itr].reverse==1)
			{
				for(int i=0;i<M;i++)
				{
					map[row][col+i]+=mStructure[M-1-i];
				}
				int temp=bfs(mSeaLevel);
				if(temp>ans) ans=temp;
				for(int i=0;i<M;i++)
				{
					map[row][col+i]-=mStructure[M-1-i];
				}
			}
		}
	}
	if(!Hash_vertical_Structures2Id[key].empty())
	{
		for(int itr:Hash_vertical_Structures2Id[key])
		{
			int row = str[itr].r, col = str[itr].c;
			if(str[itr].reverse==0)
			{
				for(int i=0;i<M;i++)
				{
					map[row+i][col]+=mStructure[i];
				}
				int temp=bfs(mSeaLevel);
				if(temp>ans) ans=temp;
				for(int i=0;i<M;i++)
				{
					map[row+i][col]-=mStructure[i];
				}
			}
			else  if(str[itr].reverse==1)
			{
				for(int i=0;i<M;i++)
				{
					map[row+i][col]+=mStructure[M-1-i];
				}
				int temp=bfs(mSeaLevel);
				if(temp>ans) ans=temp;
				for(int i=0;i<M;i++)
				{
					map[row+i][col]-=mStructure[M-1-i];
				}
			}
		}
	}
	return ans;
}