Submission #1343932

#TimeUsernameProblemLanguageResultExecution timeMemory
1343932jumpTracks in the Snow (BOI13_tracks)C++20
0 / 100
2103 ms1114112 KiB
#include <bits/stdc++.h>
#define int long long

int h,w;
std::vector<std::string> grid;
bool fill[4010][4010];
void reset(){
	for(int i=0;i<=4000;i++){
		for(int j=0;j<=4000;j++){
			fill[i][j]=false;
		}
	}
}
bool check(int x,int y,const std::string& valid){
	for(auto c:valid){
		if(grid[x][y]==c)return true;
	}
	//std::cout << x << ' ' << y << ' ' << valid << '\n';
	return false;
}
bool floodfill(int x,int y,char path,const std::string& valid){
	if(fill[x][y])return false;
	if(!check(x,y,valid))return false;
	fill[x][y]=true;
	std::vector<std::pair<int,int>> move = {{1,0},{-1,0},{0,1},{0,-1}};
	for(auto [mx,my]:move){
		int tox=mx+x;
		int toy=my+y;
		if(tox<=0||toy<=0||tox>h||toy>w)continue;
		floodfill(tox,toy,path,valid);
	}
	if(grid[x][y]!=path)fill[x][y]=false;
	return true;
}
signed main(){
	std::cin >> h >> w;
	grid.push_back("");
	for(int i=1;i<=h;i++){
		std::string str;
		std::cin >> str;
		grid.push_back("."+str);
	}
	int r=0,f=0,com=0;
	// for(int i=1;i<=h;i++){
	// 	if(floodfill(i,1,"R"))r+=1;
	// 	if(floodfill(i,w,"R"))r+=1;
	// }
	// for(int j=1;j<=w;j++){
	// 	if(floodfill(1,j,"R"))r+=1;
	// 	if(floodfill(h,j,"R"))r+=1;
	// }
	// for(int i=1;i<=h;i++){
	// 	for(int j=1;j<=w;j++){
	// 		if(fill[i][j]==false&&grid[i][j]=='R')r+=1e9;
	// 	}
	// }
	// reset();
	// for(int i=1;i<=h;i++){
	// 	if(floodfill(i,1,"F"))f+=1;
	// 	if(floodfill(i,w,"F"))f+=1;
	// }
	// for(int j=1;j<=w;j++){
	// 	if(floodfill(1,j,"F"))f+=1;
	// 	if(floodfill(h,j,"F"))f+=1;
	// }
	// for(int i=1;i<=h;i++){
	// 	for(int j=1;j<=w;j++){
	// 		if(fill[i][j]==false&&grid[i][j]=='F')f+=1e9;
	// 	}
	// }
	reset();
	for(int i=1;i<=h;i++){
		if(floodfill(i,1,'R',"RF"))com+=1;
		if(floodfill(i,w,'R',"RF"))com+=1;
		if(floodfill(i,1,'F',"RF"))com+=1;
		if(floodfill(i,w,'F',"RF"))com+=1;
	}
	for(int j=1;j<=w;j++){
		if(floodfill(1,j,'R',"RF"))com+=1;
		if(floodfill(h,j,'R',"RF"))com+=1;
		if(floodfill(1,j,'F',"RF"))com+=1;
		if(floodfill(h,j,'F',"RF"))com+=1;
	}
	//std::cout << r << ' ' << f <<'\n';
	std::cout << std::min(r,f)+com;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...