Submission #708789

#TimeUsernameProblemLanguageResultExecution timeMemory
708789myrcellaDango Maker (JOI18_dango_maker)C++17
13 / 100
21 ms44644 KiB
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 3010;

int n,m;
int grid[maxn][maxn];
bool mark[maxn][maxn];

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	memset(grid,-1,sizeof(grid));
	rep(i,0,n) {
		string s;cin>>s;
		rep(j,0,m) {
			if (s[j]=='R') grid[i][j]=0;
			else if (s[j]=='G') grid[i][j]=1;
			else grid[i][j]=2;
		}
	}
	//find G centered
	memset(mark,0,sizeof(mark));
	rep(i,1,n-1)
		rep(j,1,m-1) if (grid[i][j]==1 and grid[i-1][j]+grid[i][j-1]==0 and grid[i][j+1]+grid[i+1][j]==4) mark[i][j]=1;
	int ans = 0;
	rep(i,1,n-1)
		rep(j,1,m-1) {
			if (mark[i][j]==1) {
				int ii=i,jj = j;
				while (ii<n and jj>0 and mark[ii+1][jj-1]==1) {
					if (ii!=i) {
						grid[ii][jj-1]=grid[ii][jj]=grid[ii][jj+1]=-1;
						ans++;
					}
					ii++,jj--;
					mark[ii][jj]=0;
				}
				if (ii==i) {
					if (mark[i][j]==1) {
						int ii=i,jj = j;
						while (ii<n and jj>0 and mark[ii+1][jj-1]==1) {
							ii++,jj--;
							mark[ii][jj]=0;
						}
						int row=0,col=0;
						if (grid[i-1][j+1]==1 and grid[i-1][j+2]==2) row++;
						if (i-2>=0 and grid[i-2][j+1]==0 and grid[i-1][j+1]==1) col++;
						if (jj-2>=0 and grid[ii+1][jj-1]==1 and grid[ii+1][jj-2]==0) row++;
						if (grid[ii+1][jj-1]==1 and grid[ii+2][jj-1]==2) col++;
						int curi=i-1,curj=j+1;
						if (row>col) {
							while (curi<=ii+1) {
								if (curj-1>=0 and grid[curi][curj-1]==0 and grid[curi][curj]==1 and grid[curi][curj+1]==2) {
									grid[curi][curj-1]=grid[curi][curj]=grid[curi][curj+1]=-1;
									ans++;
								}
								curi++;
								curj--;
							}
						}
						else {
							while (curi<=ii+1) {
								if (curi-1>=0 and grid[curi-1][curj]==0 and grid[curi][curj]==1 and grid[curi+1][curj]==2) {
									grid[curi-1][curj]=grid[curi][curj]=grid[curi+1][curj]=-1;
									ans++;
								}
								curi++;
								curj--;
							}
						}
					}
				}
				else {
					if (grid[i-1][j+1]==1 and grid[i-1][j+2]==2) {
						grid[i-1][j]=grid[i-1][j+1]=grid[i-1][j+2]=-1;
						grid[i][j-1]=grid[i][j]=grid[i][j+1]=-1;
						ans+=2;
					}
					else {
						if (i-2>=0 and grid[i-2][j+1]==0 and grid[i-1][j+1]==1) {
							grid[i-2][j+1]=grid[i-1][j+1]=grid[i][j+1]=-1;
							ans++;
						}
						grid[i-1][j]=grid[i][j]=grid[i+1][j]=-1;
						ans++;
					}
					
					if (jj-2>=0 and grid[ii+1][jj-1]==1 and grid[ii+1][jj-2]==0) {
						grid[ii+1][jj]=grid[ii+1][jj-1]=grid[ii+1][jj-2]=-1;
						grid[ii-1][jj]=grid[ii][jj]=grid[ii+1][jj]=-1;
						ans+=2;
					}
					else {
						if (grid[ii+1][jj-1]==1 and grid[ii+2][jj-1]==2) {
							grid[ii+2][jj-1]=grid[ii+1][jj-1]=grid[ii][jj-1]=-1;
							ans++;
						}
						grid[ii+1][jj]=grid[ii][jj]=grid[ii-1][jj]=-1;
						ans++;
					}
				}
				
			}
		}
//	debug(ans);
	//find path
	rep(i,0,n) rep(j,0,m) {
		if (grid[i][j]!=0) continue;
		int curi=i,curj=j;
		while (1) {
			if (grid[curi+1][curj]==1 and grid[curi+2][curj]==2) {
				if (curj-2>=0 and grid[curi+2][curj-2]==0 and grid[curi+2][curj-1]==1) {
					curj-=2;
					curi+=2;
				}
				else {
					int x=i,y=j;
					while (x<=curi) {
						if (grid[x][y]==0 and grid[x+1][y]==1 and grid[x+2][y]==2) {
							ans++;
							grid[x][y] = grid[x+1][y] = grid[x+2][y] = -1;
						}
						x+=2,y-=2;
					}
					break;
				}
			}
			else {
				int x=i,y=j;
				while (x<=curi) {
					if (grid[x][y]==0 and grid[x][y+1]==1 and grid[x][y+2]==2) {
						ans++;
						grid[x][y] = grid[x][y+1] = grid[x][y+2] = -1;
					}
					x+=2,y-=2;
				}
				break;
			}
		}
	}
	/*
	debug(ans);
	rep(i,0,n)
		rep(j,0,m) {
			debug(grid[i][j]);
			if (grid[i][j]==0 and grid[i][j+1]==1 and grid[i][j+2]==2) ans++;
			if (grid[i][j]==0 and grid[i+1][j]==1 and grid[i+2][j]==2) ans++;
		}
	*/
	cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...