Submission #362956

#	Time	Username	Problem	Language	Result	Execution time	Memory
362956		CaroLinda	Cultivation (JOI17_cultivation)	C++14	5 / 100	57 ms	50412 KiB

cultivation

#include <bits/stdc++.h>

#define ll long long
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i= a ; i < b ; i++ )
#define pb push_back

const int MAX = 1048586 ;

using namespace std ;

int N , R , C , base ;
int dist[MAX] ;
int mask[5] ;
int grid[10][10] , code[10][10] ;
vector<int> adj[MAX] ;

bool isOn(int m, int i ) {  return ((1<<i)&m ) != 0 ; }
bool valid(int x, int y ) { return 0 <= min(x,y) && x < R && y < C ; }

//0 = north
//1 = east
//2 = south
//3 = west

void printGrid()
{
	for(int i = 0 ; i <R ; i++ , cout << endl )
		lp(j,0,C) cout << grid[i][j] << " " ;
	cout << endl ;
}


int get_code(int dir )
{
	pair<int,int> p = make_pair(0,0) ;

	if(dir == 0 ) p.first-- ;
	if( dir == 1 ) p.second++ ;
	if( dir == 2 ) p.first++ ;
	if( dir == 3 ) p.second-- ;

	int s = 0 ;

	for(int i = 0 ; i < R ; i++ )
		for(int j = 0 ; j < C ; j++ )
			if( ( valid(i-p.first, j-p.second) && grid[i-p.first][j-p.second] ) || grid[i][j]  )
				s += 1<<code[i][j] ;

	return s ;
}

int main()
{

	scanf("%d %d", &R, &C ) ;
	assert( R <= 4 && C <=  4 ) ;
	scanf("%d", &N ) ;

	for(int i= 0 , c = 0 ; i <R ; i++ )
		for(int j = 0 ; j< C ; j++ , c++ ) code[i][j] = c ;

	int s = 0 ;

	for(int i = 1 , x , y ; i<= N ; i++ )
	{
		scanf("%d %d", &x, &y ) ;
		x-- ; y-- ;
		s |= (1<<code[x][y] ) ;
	}

	int mx = (1<<(code[R-1][C-1]+1) ) - 1 ;
	
	for(int i= 0 ; i <= mx ; i++ )
	{
		dist[i] = 20 ;

		for(int j = 0 ; j < R ; j++ )
			for(int g = 0 ; g < C ; g++ )
				grid[j][g] = isOn(i,code[j][g] ) ;

		for(int j = 0 ; j <4 ; j++ ) adj[i].pb( get_code(j) ) ;
	}

	dist[s] = 0 ;
	vector<int> fila(1,s) ;
	int ini = 0 ;

	while( ini < sz(fila) )
	{
		int x = fila[ini++] ;

//		printGrid();

		for(auto e : adj[x] )
		{
			if( dist[e] <= dist[x] + 1 ) continue ;
			dist[e] = dist[x] + 1; 
			fila.push_back( e ) ;
		}
	}
	                            
	printf("%d\n", dist[mx] ) ; 
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d %d", &R, &C ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
cultivation.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
cultivation.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d %d", &x, &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20