Submission #733566

#	Time	Username	Problem	Language	Result	Execution time	Memory
733566		lucasSala	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	736 ms	119104 KiB

tracks

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

const int MAX = 4e3+4;

char matriz[MAX][MAX];
int dist[MAX][MAX];

int n,m;

bool inBound(pair<int,int> a){
    int x = a.first, y = a.second;
    if(x < 0 or x >= n or y < 0 or y >= m or matriz[x][y] == '.' or dist[x][y] > 0){
        return false;
    }
    return true;
}

int main(){ios_base::sync_with_stdio(false); cin.tie(NULL);
    int ans = 1;
    cin >> n >> m;
    for(int i =0;i < n;i++){
        for(int j = 0; j < m;j++){
            cin >> matriz[i][j];
        }
    }
    deque<pair<int,int>> fila;
    dist[0][0] =1;
    fila.push_front({0,0});
    while(!fila.empty()){
        pair<int,int> atual = fila.front();
        fila.pop_front();
        int x = atual.first, y = atual.second;
        ans = max(ans,dist[x][y]);
        if(inBound({x+1,y})){
            if(matriz[x+1][y] == matriz[x][y]){
                dist[x+1][y] = dist[x][y];
                fila.push_front({x+1,y});
            }
            else{
                dist[x+1][y] = dist[x][y]+1;
                fila.push_back({x+1,y});
            }
        }
        if(inBound({x-1,y})){
            if(matriz[x-1][y] == matriz[x][y]){
                dist[x-1][y] = dist[x][y];
                fila.push_front({x-1,y});
            }
            else{
                dist[x-1][y] = dist[x][y]+1;
                fila.push_back({x-1,y});
            }
        }
        if(inBound({x,y+1})){
            if(matriz[x][y+1] == matriz[x][y]){
                dist[x][y+1] = dist[x][y];
                fila.push_front({x,y+1});
            }
            else{
                dist[x][y+1] = dist[x][y]+1;
                fila.push_back({x,y+1});
            }
        }
        if(inBound({x,y-1})){
            if(matriz[x][y-1] == matriz[x][y]){
                dist[x][y-1] = dist[x][y];
                fila.push_front({x,y-1});
            }
            else{
                dist[x][y-1] = dist[x][y]+1;
                fila.push_back({x,y-1});
            }
        }
    }
    cout << max(ans,dist[n-1][m-1]);
}

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