Submission #199452

#	Time	Username	Problem	Language	Result	Execution time	Memory
199452		TadijaSebez	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	726 ms	112692 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int N=4050;
char s[N][N];
int dist[N][N],n,m;
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool ok(int x,int y){return x>=1 && x<=n && y>=1 && y<=m && s[x][y]!='.';}
int main(){
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dist[i][j]=1e9;
	deque<int> q;
	q.push_back(1*N+1);
	dist[1][1]=1;
	int ans=0;
	while(q.size()){
		int x=q.front()/N;
		int y=q.front()%N;
		q.pop_front();
		ans=max(ans,dist[x][y]);
		for(int k=0;k<4;k++){
			int i=x+mv[k][0];
			int j=y+mv[k][1];
			if(ok(i,j)){
				int w=s[x][y]!=s[i][j];
				if(dist[i][j]>dist[x][y]+w){
					dist[i][j]=dist[x][y]+w;
					if(w==0)q.push_front(i*N+j);
					else q.push_back(i*N+j);
				}
			}
		}
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:10:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
                       ~~~~~^~~~~~~~~~~~~

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