제출 #1161132

#제출 시각아이디문제언어결과실행 시간메모리
1161132elotelo966Dango Maker (JOI18_dango_maker)C++20
0 / 100
128 ms327680 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define pb push_back
#define lim 3005

int n,m,cev,maxi,cur1,cur2;

char dizi[lim][lim];

vector<int> v[lim*lim*2];
int vis[lim*lim*2];

inline int ind(int x,int y,int z){
	return n*m*z+(x-1)*m+y;
}

inline bool check(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m;
}

inline bool check_left(int x,int y){
	return check(x,y) && check(x,y+1) && check(x,y+2) && dizi[x][y]=='R' && dizi[x][y+1]=='G' && dizi[x][y+2]=='W';
}

inline bool check_top(int x,int y){
	return check(x,y) && check(x+1,y) && check(x+2,y) && dizi[x][y]=='R' && dizi[x+1][y]=='G' && dizi[x+2][y]=='W';
}

inline void dfs(int node){
	//cout<<node<<endl;
	maxi=max(maxi,max(cur1,cur2));
	for(auto go:v[node]){
		if(!vis[go]){
			if(vis[node]==1){
				vis[go]=2;
                cur2++;
				dfs(go);
			}
			else{
				vis[go]=1;
                cur1++;
				dfs(go);
			}
		}
	}
} 

int32_t main(){
	faster
	cin>>n>>m;
	FOR{
		string s;cin>>s;
		for(int j=0;j<m;j++){
			dizi[i][j+1]=s[j];
		}
	}
	
	FOR{
		for(int j=1;j<=m;j++){
			if(check_left(i,j)){
				if(check_top(i,j))v[ind(i,j,0)].pb(ind(i,j,1));
				if(check_top(i-1,j+1))v[ind(i,j,0)].pb(ind(i-1,j+1,1));
				if(check_top(i-2,j+2))v[ind(i,j,0)].pb(ind(i-2,j+2,1));
			}
			if(check_top(i,j)){
				if(check_left(i,j))v[ind(i,j,1)].pb(ind(i,j,0));
				if(check_left(i+1,j-1))v[ind(i,j,1)].pb(ind(i+1,j-1,0));
				if(check_left(i+2,j-2))v[ind(i,j,1)].pb(ind(i+2,j-2,0));
			}
		}
	}
	
	FOR{
		for(int j=1;j<=m;j++){
			if(check_left(i,j) && !vis[ind(i,j,0)]){
				maxi=0;
				vis[ind(i,j,0)]=1;
                cur1=1,cur2=0;
				dfs(ind(i,j,0));
				cev+=maxi;
			}
			if(check_top(i,j) && !vis[ind(i,j,1)]){
				maxi=0;
				vis[ind(i,j,1)]=1;
                cur1=1,cur2=0;
				dfs(ind(i,j,1));
				cev+=maxi;
			}
			//if(ind(i,j,1)>lim*lim*5 || ind(i,j,1)<1)cout<<i<<" "<<j<<" "<<1<<endl;
			//if(ind(i,j,0)>lim*lim*5 || ind(i,j,0)<1)cout<<i<<" "<<j<<" "<<0<<endl;
			//cout<<i<<" "<<j<<" "<<maxi<<endl;
		}
	}
	
	cout<<cev<<'\n';
	
	return 0;
}

/*
 * 
 * 
RRRR
RRGW
RGWR
RGWW

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...