Submission #346467

#	Time	Username	Problem	Language	Result	Execution time	Memory
346467		ahmet	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1242 ms	227452 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ref(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define rep(a,b) for(int (a)=0;(a)<(b);++(a))
#define pb push_back
#define mp make_pair
const int mx=5000;
int n,m;
char a[mx][mx];
int depth[mx][mx];
int vis[mx][mx];
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int check(int x,int y){
	if(x==0 or y==0 or x==n+1 or y==m+1 or a[x][y]=='.' or vis[x][y])return 1;
	else return 0;
}
int ans=1;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin >> a[i][j];
		}
	}
	rep(i,mx)rep(j,mx)depth[i][j]=2e9;
	depth[1][1]=1;
	deque <pair <int,int> > q;
	q.push_front(mp(1,1));
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop_front();
		if(vis[x][y])continue;
		else vis[x][y]=1;
		//cout << x << " " << y << " " << depth[x][y] << endl;
		//if(x==1 and y==5)cout<<"BURda";
		ans=max(ans,depth[x][y]);
		for(int i=0;i<4;++i){
			int gox=x+dx[i];int goy=y+dy[i];
		//	if(x==1 and y==5)cout<<gox << " " << goy << endl;
			if(check(gox,goy))continue;
			if(a[gox][goy]==a[x][y] and depth[gox][goy]>depth[x][y]){
				depth[gox][goy]=depth[x][y];
				q.push_front(mp(gox,goy));
			//	if(x==1 and y==5)cout<<"BURDa  1 " << i << endl;
			}
			else if(a[gox][goy]!=a[x][y] and depth[gox][goy]>depth[x][y]+1){
				depth[gox][goy]=depth[x][y]+1;
				q.push_back(mp(gox,goy));
				//if(x==1 and y==5)cout<<"BURDa 2  " << i << endl;
			}
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
      |                          ^
tracks.cpp:28:2: note: in expansion of macro 'rep'
   28 |  rep(i,mx)rep(j,mx)depth[i][j]=2e9;
      |  ^~~
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
      |                          ^
tracks.cpp:28:11: note: in expansion of macro 'rep'
   28 |  rep(i,mx)rep(j,mx)depth[i][j]=2e9;
      |           ^~~

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