Submission #992100

#	Time	Username	Problem	Language	Result	Execution time	Memory
992100		ahoraSoyPeor	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1739 ms	342904 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;

const int S = 4000;
char meadow[S][S];
int dist[S][S];
bool vis[S][S];
const int INF = 1e8;

void reset(){
	for(int i = 0; i < S; i++){
		for(int j = 0; j < S; j++){
			dist[i][j] = INF;
		}
	}
}

const int delta_X[] = {-1, 1, 0, 0};
const int delta_Y[] = {0, 0, -1, 1};

bool is_in ( pii cell, int h, int w ) {
    return cell.ff >= 0 and cell.ss >= 0 and cell.ff < h and cell.ss < w;
}

int solve(int h, int w){

	reset();
	int ans = 0;
	pii start = {0,0};
	deque<pii> dq;
	dq.push_back(start);
	dist[0][0] = 0;
	while(dq.size()){
		auto [a, b] = dq.front(); dq.pop_front();
		
		if(vis[a][b]) continue;
		vis[a][b] = true;
		char animal = meadow[a][b];
		// obtener vecinos
		vector<pii> vecinos;
        for ( int i = 0; i < 4; ++i ) {
            pii nxt_cell = {a+delta_X[i], b+delta_Y[i]};
            if ( !is_in ( nxt_cell, h, w ) ) continue;
            char animal_cell = meadow[nxt_cell.ff][nxt_cell.ss];
            if ( animal_cell != '.' )
                vecinos.pb ( nxt_cell );
        }
		
		// iterar por vecinos
		for(auto [x,y]: vecinos){
			int d = 0;
			if(meadow[x][y] != animal){
				d = 1;
			}
			// if (dist[curr_node] + d > dist[to]) continue;
			if(dist[a][b] + d > dist[x][y]) continue;
			
			dist[x][y] = dist[a][b] + d;
			
			ans = max(ans, dist[x][y]);
			
			if(d == 1){
				dq.push_back({x,y});
			}
			else if(d == 0){
				dq.push_front({x,y});
			}
		}
		
	}
	return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int h, w; cin >> h >> w;
  

  for(int i = 0; i < h; ++i){
	  for(int j = 0; j < w; ++j){
		  char x; cin >> x;
		  meadow[i][j] = x;
	  }
  }
  cout << solve(h,w)+1; 
}

/*
 * 
 * 5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

5 5
FRFRF
RRFRF
FFFRF
RRRRF
FFFFF
 */

Compilation message (stderr)

tracks.cpp: In function 'int solve(int, int)':
tracks.cpp:41:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto [a, b] = dq.front(); dq.pop_front();
      |        ^
tracks.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   for(auto [x,y]: vecinos){
      |            ^

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