제출 #1152075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152075		Richard_Dyinman	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	504 ms	144824 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];
deque<pair<int, pair<int, int>>> q;
void bfs(){
    while(!q.empty()){
        auto [cnt , node] = q.front();
        q.pop_front();
        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]);
                if(arr[x][y] != arr[x - 1][y]){
                    q.push_back({fin[x - 1][y], {x - 1, y}});
                }else{
                    q.push_front({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]);
                if(arr[x][y] != arr[x + 1][y]){
                    q.push_back({fin[x + 1][y], {x + 1, y}});
                }else{
                    q.push_front({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]);
                if(arr[x][y] != arr[x][y + 1]){
                    q.push_back({fin[x][y + 1], {x, y + 1}});
                }else{
                    q.push_front({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]);
                if(arr[x][y] != arr[x][y - 1]){
                    q.push_back({fin[x][y - 1], {x, y - 1}});
                }else{
                    q.push_front({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_back({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;
//#ifndef ONLINE_JUDGE
//    OJudge(IN.c_str(),OUT.c_str());
//#endif
    bool test = 0;
    if (test)
        cin>>tc;
    else tc = 1;
    for (int i = 1; i<=tc; i++){
        solve();
    }
}

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