제출 #1343910

#제출 시각아이디문제언어결과실행 시간메모리
1343910jumpTracks in the Snow (BOI13_tracks)C++20
0 / 100
2146 ms1114112 KiB
#include <bits/stdc++.h>
#define int long long

int h,w;
std::vector<std::string> grid;
bool fill[4510][4510];
void reset(){
	for(int i=0;i<=4500;i++){
		for(int j=0;j<=4500;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,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,valid);
	}
	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;
	reset();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(floodfill(i,j,"R"))r+=1;
		}
	}
	reset();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(floodfill(i,j,"F"))f+=1;
		}
	}
	reset();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(floodfill(i,j,"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...