Submission #133991

#	Time	Username	Problem	Language	Result	Execution time	Memory
133991		CaroLinda	Tracks in the Snow (BOI13_tracks)	C++14	89.06 / 100	2089 ms	623308 KiB

tracks

#include <bits/stdc++.h>

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

using namespace std ;

int n , m ;
int mat[MAXN][MAXN] , id[MAXN][MAXN] ;
int dx[4] = {1,0,-1,0} ;
int dy[4] = {0,-1,0,1} ;



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)
		{
			char c ;
			scanf(" %c", &c ) ;
			if(c=='.') mat[i][j] = -1 ;
			else mat[i][j] = (c=='R'?0:1);
		}

	vector<pii> firstGroup , secondGroup ;

	firstGroup.pb( pii(0,0) ) ;
	int ini = 0 ;
	lp(i,0,n)
		lp(j,0,m)
			id[i][j] = MAXN+10 ;
	id[0][0] = 1 ;
	int s = 0 ;

	while( firstGroup.size() != 0 )
	{
		secondGroup.resize(0) ;
		s++ ;
		ini = 0 ;
		while( ini < firstGroup.size() )
		{
			pii p = firstGroup[ini++] ;

			for(int i = 0 ; i < 4 ; i++)
			{
				int x = p.ff + dx[i] ;
				int y = p.ss + dy[i] ;
				if( !valid(x,y) || id[x][y] != (MAXN+10) ) continue ;

				if( mat[x][y] == mat[p.ff][p.ss] )
				{
					id[x][y] = id[p.ff][p.ss] ;
					firstGroup.pb( pii(x,y) ) ;
				}
				else if ( mat[x][y] == !mat[p.ff][p.ss] )
				{
					id[x][y] = id[p.ff][p.ss] + 1 ;
					secondGroup.pb( pii(x,y) ) ;
				}
			}

		}

		firstGroup.resize(0) ;

		lp(i,0,secondGroup.size() )
			firstGroup.pb( secondGroup[i] ) ;

	}

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

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:49:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while( ini < firstGroup.size() )
          ~~~~^~~~~~~~~~~~~~~~~~~
tracks.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
tracks.cpp:75:6:
   lp(i,0,secondGroup.size() )
      ~~~~~~~~~~~~~~~~~~~~~~     
tracks.cpp:75:3: note: in expansion of macro 'lp'
   lp(i,0,secondGroup.size() )
   ^~
tracks.cpp:24: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:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &c ) ;
    ~~~~~^~~~~~~~~~~~

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