Submission #133996

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

tracks

#include <bits/stdc++.h>

#define MAXN 4005
#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> group[2];

	group[0].pb( pii(0,0) ) ;
	id[0][0] = 1 ;
	int s = 0 , ini , j = 0 ;

	while( group[j].size() != 0 )
	{
		group[!j].resize(0) ;
		s++ ;
		ini = 0 ;
		while( ini < group[j].size() )
		{
			pii p = group[j][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] > 0 && id[x][y] <= id[p.ff][p.ss] ) ) continue ;

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

		}

		j = !j ;

	}

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

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while( ini < group[j].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