//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
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]) {
int ii=i,jj = j;
while (ii<n and jj>0 and mark[ii+1][jj-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 (j-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++;
}
}
}
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]=-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 time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
35668 KB |
Output is correct |
| 2 |
Correct |
16 ms |
35696 KB |
Output is correct |
| 3 |
Correct |
15 ms |
35696 KB |
Output is correct |
| 4 |
Correct |
19 ms |
35780 KB |
Output is correct |
| 5 |
Correct |
15 ms |
35668 KB |
Output is correct |
| 6 |
Execution timed out |
2077 ms |
35784 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
35668 KB |
Output is correct |
| 2 |
Correct |
16 ms |
35696 KB |
Output is correct |
| 3 |
Correct |
15 ms |
35696 KB |
Output is correct |
| 4 |
Correct |
19 ms |
35780 KB |
Output is correct |
| 5 |
Correct |
15 ms |
35668 KB |
Output is correct |
| 6 |
Execution timed out |
2077 ms |
35784 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
35668 KB |
Output is correct |
| 2 |
Correct |
16 ms |
35696 KB |
Output is correct |
| 3 |
Correct |
15 ms |
35696 KB |
Output is correct |
| 4 |
Correct |
19 ms |
35780 KB |
Output is correct |
| 5 |
Correct |
15 ms |
35668 KB |
Output is correct |
| 6 |
Execution timed out |
2077 ms |
35784 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
