제출 #443964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443964		Autron	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1473 ms	123784 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

int n, m;
char a[4002][4002];
int dist[4002][4002];
int dx[4]={1,-1,0,0};
int dy[4]={0, 0,1,-1};

int isok(int x, int y){
	return (0<x)&&(x<=n)&&(0<y)&&(y<=m)&&(dist[x][y]==0);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
		}
	}
	deque<pair<int, int>> q;
	q.push_back({1, 1});
	dist[1][1]=1;
	int sol=0;
	while(!q.empty()){
		int x, y;
		tie(x, y)=q.front();
		q.pop_front();
		for(int k=0;k<4;++k){
			int nx=x+dx[k], ny=y+dy[k];
			if(isok(nx, ny)){
				if(a[nx][ny]=='.') continue;
				if(a[nx][ny]==a[x][y]){
					dist[nx][ny]=dist[x][y];
					sol=max(sol, dist[nx][ny]);
					q.push_front({nx, ny});
				}
				else{	
					dist[nx][ny]=dist[x][y]+1;
					sol=max(sol, dist[nx][ny]);
					q.push_back({nx, ny});
				}
			}
		}
	}
	cout<<sol<<"\n";
}

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