제출 #1147381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147381		sangiko	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	578 ms	129548 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

#define r first
#define c second

int n,m;
const int maxn = 4100;
string grid[maxn];
int d[maxn][maxn];
int ans = 1;
//UDLR
int dr[] = {1,-1,0,0};
int dc[] = {0,0,-1,1};

bool check(pair<int,int> u){
    return u.r >= 0 && u.r < n && u.c >= 0 && u.c < m && grid[u.r][u.c] != '.';
}

void dfs(pair<int,int> s){
    d[s.r][s.c] = 1;
    deque<pair<int,int>> next;
    next.push_front(s);

    while(!next.empty()){
        pair<int,int> u = next.front();
        next.pop_front();

        ans = max(ans,d[u.r][u.c]);

//        cerr << "(r,c): " << u.r << " " << u.c << " d: " << d[u.r][u.c] << "\n";

        for(int i = 0;i < 4;++i){
            pair<int,int> v = {u.r + dr[i],u.c + dc[i]};
            if(check(v) && d[v.r][v.c] == 0){
                if(grid[u.r][u.c] == grid[v.r][v.c]){
                    d[v.r][v.c] = d[u.r][u.c];
                    next.push_front(v);
                } else {
                    d[v.r][v.c] = d[u.r][u.c] + 1;
                    next.push_back(v);
                }
            }
        }

    }
}

int main(){

    cin >> n >> m;

    for(int i = 0;i < n;++i){
        cin >> grid[i];
    }

    memset(d,0,sizeof(d));
    dfs({0,0});

    cout << ans << "\n";

    return 0;
}

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