Submission #1136697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136697		Richard_Dyinman	Tracks in the Snow (BOI13_tracks)	C++20	69.38 / 100	2099 ms	84236 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()

#define file \
  freopen("guard.in", "r", stdin);\
  freopen("guard.out", "w", stdout)

#define OJudge(in,out) \
      freopen(in, "r", stdin);\
      freopen(out, "w", stdout)


#define FIn   \
  cin.tie(0); \
  cout.tie(0); \
  ios_base::sync_with_stdio(false)

const string IN = "input.txt";
const string OUT = "output.txt";
int  tc;
ll n,m,a,b,c,k;
char arr[4100][4100];
int fin[4100][4100];
queue<pair<int, pair<int, int>>> q;
void bfs(){
    while(!q.empty()){
        auto [cnt , node] = q.front();
        q.pop();
        int x = node.first;
        int y = node.second;
        if(x > 0){
            if(arr[x - 1][y] != '.' && fin[x-1][y] > cnt + (arr[x][y] != arr[x - 1][y])){
                fin[x-1][y] = cnt + (arr[x][y] != arr[x - 1][y]);
                q.push({fin[x-1][y] , {x-1 , y}});
            }
        }
        if(x < n-1){
            if(arr[x + 1][y] != '.' && fin[x + 1][y] > cnt + (arr[x][y] != arr[x + 1][y])){
                fin[x + 1][y] = cnt + (arr[x][y] != arr[x + 1][y]);
                q.push({fin[x+1][y] , {x+1 , y}});
            }
        }
        if(y < m-1){
            if(arr[x][y + 1] != '.' && fin[x][y + 1] > cnt + (arr[x][y] != arr[x][y + 1])){
                fin[x][y + 1] = cnt + (arr[x][y] != arr[x][y + 1]);
                q.push({fin[x][y + 1] , {x , y + 1}});
            }
        }
        if(y > 0){
            if(arr[x][y - 1] != '.' && fin[x][y - 1] > cnt + (arr[x][y] != arr[x][y - 1])){
                fin[x][y - 1] = cnt + (arr[x][y] != arr[x][y - 1]);
                q.push({fin[x][y - 1] , {x , y - 1}});
            }
        }
    }
}


void solve() {
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin>>arr[i][j];
            fin[i][j] = 1e9;
        }
    }
    q.push({1, {0,0}});
    bfs();
    int rslt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(arr[i][j] != '.')
                rslt = max(rslt , fin[i][j]);
        }
    }
    cout<<rslt;
}

int main() {
    FIn;
    //file;
    bool test = 0;
    if (test)
        cin>>tc;
    else tc = 1;
    for (int i = 1; i<=tc; i++){
        solve();
    }
}

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