Submission #708769

#	Time	Username	Problem	Language	Result	Execution time	Memory
708769		myrcella	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	21 ms	44692 KiB

dango_maker

//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 cntr,cntc;

void dfs(int x,int y) {
	
}

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) {
					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;
							mark[curi][curj]=0;
							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;
							mark[curi][curj]=0;
							ans++;
						}
						curi++;
						curj--;
					}
				}
			}
		}
//	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;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67