Submission #1032534

#TimeUsernameProblemLanguageResultExecution timeMemory
1032534hippo123Tracks in the Snow (BOI13_tracks)C++17
49.69 / 100
2074 ms1048576 KiB
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pr pair<ll, ll>
#define f first
#define s second
#define pb push_back
const int ndim=4001;
int ns;
vector<vector<int>> d(ndim, vector<int>(ndim));

void floodfill(int x, int y, int h, int w, int col){
	// out of bound
	// count & change color
	ns++; d[x][y]^=1;
	
	if(x==h-1 && y==w-1) return; 
	
	
	int dx[4]={1, -1, 0, 0};
	int dy[4]={0, 0, 1, -1};
	
	for (int i=0; i<4; i++){
		int x1=x+dx[i]; int y1=y+dy[i];
		
		if(x1>=0 && x1<h && y1>=0 && y1<w){
			if(d[x1][y1]==col) {
				floodfill(x1, y1, h, w, col); 
			}
		}	
	}
	
}

int main(){
	int h, w; cin>>h>>w;
	//vector<vector<int>> d(h, vector<int> (w, -1));
	int nf=0;
	for (int i=0; i<h; i++){
		string s; cin>>s;
		for (int j=0; j<w; j++){
			if(s[j]=='.') {
				d[i][j]=-1; continue;
			} 
			nf++;
			if(s[j]=='R') d[i][j]=0;
			else d[i][j]=1; 
		}
	}

	//for (int i=0; i<h; i++){
	//	for (int j=0; j<w; j++) cout<<d[i][j]<<" ";
	//	cout<<endl;
	//}
	
	
	ns=0;
	int cnt=0; 
	while(ns<nf){
		ns=0; cnt++; 
		floodfill(0, 0, h, w, d[0][0]);		
		
		if(ns==nf) break;
	}
	cout<<cnt<<endl;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...