제출 #1032544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032544		hippo123	Tracks in the Snow (BOI13_tracks)	C++17	56.25 / 100	2131 ms	1048576 KiB

tracks

#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));
map<pr, int> ms; 
vector<vector<bool>> vis(ndim, vector<bool>(ndim, false));
vector<set<int>> adj(2e5);



int h, w; 



	int dx[4]={1, -1, 0, 0}; 
	int dy[4]={0, 0, 1, -1};

void dfs(int x, int y, int col, int num){
	if(x<0 || x>=h || y<0 || y>=w ) return; 
	if(d[x][y]!=col || vis[x][y]) return;
	
	//cout<<" x/y= "<<x<<" "<<y<<endl;
	
	ms[{x,y}]=num; 
	vis[x][y]=true;
	
	for (int i=0; i<4; i++){
		int xn=x+dx[i]; int yn=y+dy[i]; 
		dfs(xn, yn, col, num);
	} 
}

void dfs1(int x, int y, int col, int num){
	if(x<0 || x>=h || y<0 || y>=w ) return; 
	if(d[x][y]!=col || vis[x][y]) return;
	
	//cout<<" x/y= "<<x<<" "<<y<<endl;
	vis[x][y]=true;
	
	for (int i=0; i<4; i++){
		
		int xn=x+dx[i]; int yn=y+dy[i]; 
		if(xn<0 || xn>=h || yn<0 || yn>=w ) continue;
		if(d[xn][yn]==-1) continue; 
		if(d[xn][yn]!=d[x][y]){
			adj[ms[{xn, yn}]].insert(ms[{x, y}]);
			adj[ms[{x, y}]].insert(ms[{xn, yn}]);
		}
		
		dfs1(xn, yn, col, num);
	} 
}

int main(){
	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;
	//}
	int num=0;
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++){
			if((d[i][j]!=-1) & (!vis[i][j])) {
				dfs(i, j, d[i][j], num); 
				num++;
			}
		}
	}
	//cout<<" we are here"<<endl;
	//==============
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++) vis[i][j]=false;
	}
	
	for (int i=0; i<h; i++){
		for (int j=0; j<w; j++){
			if((d[i][j]!=-1) & (!vis[i][j])) {
				dfs1(i, j, d[i][j], num); 
			}
		}
	}
	//cout<<" we are here"<<endl;
	
	//for (int i=0; i<num; i++) {
	//	for (auto e: adj[i]) cout<<e<<" ";
	//	cout<<endl;
	//}
	
	
	vector<bool> vis1(num, false);
	vector<int> level(num, -1);
	queue<pr> q; q.push({0, 0}); // node, lev
	level[0]=0;
	int lv_max=0;
	while (!q.empty()){
		pr nd=q.front(); q.pop();
		int node=nd.f; int lev=nd.s;
		for (int elem: adj[node]){
			//cout<<" elem= "<<elem<<endl;
			if(level[elem]==-1){
				level[elem]=lev+1; q.push({elem, lev+1}); 				
				lv_max=max(lv_max, lev+1);
			}
		}
	}
	cout<<lv_max+1<<endl;
	
}

• Subtask 1: 30 / 30
• Subtask 2: 26.25 / 70