제출 #1315634

#제출 시각아이디문제언어결과실행 시간메모리
1315634JuanJLDango Maker (JOI18_dango_maker)C++20
33 / 100
2093 ms9392 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

string o = "RGW";

int main(){
	ll n,m; cin>>n>>m;
	vector<string> s(n); forn(i,0,n) cin>>s[i];

	//cout<<"precalculos listos\n";

	ll res = 0;
	while(true){

		vector<pair<ll,ll>> ver;
		vector<pair<ll,ll>> hor;
		forn(i,0,n){
			forn(j,0,m){
				bool vert = true;
				bool hori = true;
				forn(h,0,3){
					if(i+h>=n || s[i+h][j]!=o[h]) vert=false;
					if(j+h>=m || s[i][j+h]!=o[h]) hori=false;
				}
		
				if(vert) ver.pb({i,j}) ;//, cout<<"vert "<<i<<" "<<j<<'\n';
				if(hori) hor.pb({i,j}) ;//, cout<<"hori "<<i<<" "<<j<<'\n';
			}
		}
		
		vector<pair<ll,pair<ll,ll>>> opc;
		pair<ll,pair<ll,ll>> best = {100000,{1000,1000}};
		forn(i,0,SZ(ver)){
			ll cnt = 0;
			ll j1=lower_bound(ALL(hor),ver[i])-hor.begin();
			if(j1!=SZ(hor) && hor[j1]==ver[i]) cnt++;
			
			ll j2=lower_bound(ALL(hor),pair<ll,ll>{ver[i].fst+1,ver[i].snd-1}) - hor.begin();
			if(j2!=SZ(hor) && hor[j2]==pair<ll,ll>{ver[i].fst+1,ver[i].snd-1}) cnt++;

			ll j3=lower_bound(ALL(hor),pair<ll,ll>{ver[i].fst+2,ver[i].snd-2}) - hor.begin();
			if(j3!=SZ(hor) && hor[j3]==pair<ll,ll>{ver[i].fst+2,ver[i].snd-2}) cnt++;

			opc.pb({cnt,{0,i}});
			best=min(best,{cnt,{0,i}});
		}

		//cout<<"intersecciones verticales listas\n";

		forn(i,0,SZ(hor)){
			ll cnt = 0;
			ll j1=lower_bound(ALL(ver),hor[i])-ver.begin();
			if(j1!=SZ(ver) && ver[j1]==hor[i]) cnt++;
				
			ll j2=lower_bound(ALL(ver),pair<ll,ll>{hor[i].fst-1,hor[i].snd+1}) - ver.begin();
			if(j2!=SZ(ver) && ver[j2]==pair<ll,ll>{hor[i].fst-1,hor[i].snd+1}) cnt++;

			ll j3=lower_bound(ALL(ver),pair<ll,ll>{hor[i].fst-2,hor[i].snd+2}) - ver.begin();
			if(j3!=SZ(ver) && ver[j3]==pair<ll,ll>{hor[i].fst-2,hor[i].snd+2}) cnt++;
		
			opc.pb({cnt,{0,i}});
			best=min(best,{cnt,{1,i}});
		}

		//cout<<"intersecciones horizontales listas\n";

		//cout<<best.fst<<" "<<best.snd.fst<<" "<<best.snd.snd<<'\n';

		if(best.fst!=100000){
			res++;
			if(best.snd.fst==0){
				forn(h,0,3){
					s[ver[best.snd.snd].fst+h][ver[best.snd.snd].snd]='-';
				}
				ver.erase(ver.begin()+best.snd.snd);
			}else{
				forn(h,0,3){
					s[hor[best.snd.snd].fst][hor[best.snd.snd].snd+h]='-';
				}
				hor.erase(hor.begin()+best.snd.snd);
			}
		}else{
			break;
		}
	}

	cout<<res<<'\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...