Submission #134848

#	Time	Username	Problem	Language	Result	Execution time	Memory
134848		CaroLinda	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1729 ms	121604 KiB

tracks

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int inf = 0x3f3f3f3f ;
const int MAXN = 4123 ;

using namespace std ;

int n , m ;
int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1} ;
int d[MAXN][MAXN] ;
char mat[MAXN][MAXN] ;
deque<pii> fila ;

bool valid(int x, int y) { return (x>=0 && x<n && y>=0 && y<m) ; }

int main()
{
	scanf("%d%d",&n,&m) ;
	lp(i,0,n)
		lp(j,0,m) 
			scanf(" %c", &mat[i][j]) , d[i][j] =inf;

	fila.push_front(mk(0,0)) ;
	d[0][0] = 1 ;
	int ans = 0 ;

	while(!fila.empty())
	{
		pii p = fila.front() ;

		fila.pop_front() ;

		ans=max(ans,d[p.ff][p.ss]) ;

		lp(i,0,4)
		{
			int x = p.ff+dx[i] , y = p.ss+dy[i] ;
			
			if(!valid(x,y) || mat[x][y] =='.' ) continue ;

			if( mat[p.ff][p.ss] == mat[x][y] ){
				if(d[x][y] > d[p.ff][p.ss])
				{
					d[x][y] = d[p.ff][p.ss] ;
					fila.push_front(mk(x,y)); 
				}
			}

			else if(mat[p.ff][p.ss] != mat[x][y])
				if( (d[p.ff][p.ss]+1) < d[x][y] )
				{
					d[x][y] = d[p.ff][p.ss]+1;
					fila.push_back(mk(x,y)) ;
				}
		}
	}

	printf("%d\n", ans ) ;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m) ;
  ~~~~~^~~~~~~~~~~~~~
tracks.cpp:29:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &mat[i][j]) , d[i][j] =inf;
    ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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