제출 #1289600

#제출 시각아이디문제언어결과실행 시간메모리
1289600mefe123Dango Maker (JOI18_dango_maker)C++20
13 / 100
1 ms580 KiB
#include <iostream> 
		#include <vector> 
		#include <string> 
		#include <algorithm>
		#include <cmath> 
		#include <map>			
		#include <set>
		#include <queue>	
		#include <stack>
		#include <unordered_map>
		#include <unordered_set>
		#include <bitset>
		#include <numeric> 
		#include <functional>
		#include <iomanip>
		#include <sstream>
		#include <numeric>


				#define int long long
				#define pb push_back
				
				#define b begin()
				#define e end()
				#define fi first
				#define se second
				#define makep make_pair
					
				using namespace std;
				
				int mod=1e9+7;
				int l=0;
				int r=0;
				
				void ai(vector<int> &v){
					for(auto &go : v){
						cin>>go;
					}
				}
				void yesno(int k){
					if(k==1){
						cout<<"Yes";
					}
					else{
						cout<<"No";
					}
				}
				vector<int> vivi;
				void dfs(int node,vector<vector<int>> &adj,vector<int> &viss, int ayrac){
					viss[node]=1;
					
					if(node<ayrac){
						if(vivi[node]==0){
								l++;
								vivi[node]=1;
						}
					
					}
					else{
						if(vivi[node]==0){
								r++;
								vivi[node]=1;
						}
					}
					for(auto go:adj[node]){
						if(viss[go]==0){
							dfs(go,adj,viss,ayrac);
						}
					}
				}

				void solve(){
					int n,m;
					cin>>n>>m;
					vector<vector<char>> arr(n,vector<char>(m));
					vector<vector<int>> vis(n,vector<int>(m));
					for(int i=0;i<n;i++){
						for(int j=0;j<m;j++){
							cin>>arr[i][j];
						}
					}
					int cevap=0;
					int vissayac=1;
					for(int i=0;i<n;i++){
						for(int j=0;j<m-2;j++){
							if(arr[i][j]=='R'&&arr[i][j+1]=='G'&&arr[i][j+2]=='W'){
								//cevap++;
								vis[i][j]=vissayac;
								vis[i][j+1]=vissayac;
								vis[i][j+2]=vissayac;
								vissayac++;
								//cout<<"SS"<<i<<" "<<j<<endl;
							}
						}
					}
					vector<vector<int>> adj(n*m*2);
					int ayrac=vissayac;
					for(int j=0;j<m;j++){
						for(int i=0;i<n-2;i++){
							if(arr[i][j]=='R'&&arr[i+1][j]=='G'&&arr[i+2][j]=='W'){
								if(vis[i][j]==0&&vis[i+1][j]==0&&vis[i+2][j]==0){
									
								}
								if(vis[i][j]!=0){
									adj[vis[i][j]].pb(vissayac);
									adj[vissayac].pb(vis[i][j]);
								}
								if(vis[i+1][j]!=0){
									adj[vis[i+1][j]].pb(vissayac);
									adj[vissayac].pb(vis[i+1][j]);
									}
									if(vis[i+2][j]!=0){
										adj[vis[i+2][j]].pb(vissayac);
										adj[vissayac].pb(vis[i+2][j]);
									}
									vissayac++;
									//cout<<"YA"<<i<<" "<<j<<endl;
								}
							}
						}
						vector<int> viss(vissayac+10,0);
						vivi.resize(vissayac+10,0);
						for(int i=1;i<vissayac;i++){
							if(viss[i]==0){
								l=0;
								r=0;
								dfs(i,adj,viss,ayrac);
								cevap+=l;
								if(l<r){
									cevap-=l;
									cevap+=r;
								}
							}	
						}
						cout<<cevap;
					

					}

					signed main(){
						ios::sync_with_stdio(false);
						cin.tie(nullptr);
						int t=1;
						//cin>>t;
						while(t--){
							solve();
						}
					}
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...