제출 #1120426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120426		raul2008487	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	969 ms	324400 KiB

tracks

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;
const int sz =  4005; /// mind this
const int MAX = 2e6 + 123;
const int BS = 61;
const int mod = 998244353;

bool used[sz][sz];
char c[sz][sz];
deque<array<ll, 3>> bfs;
vector<array<ll, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve(){
    ll n, m, i, j, cnt = 0, ans = 0;
    cin >> n >> m;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            cin >> c[i][j];
            if(c[i][j] != '.'){
                cnt ++;
            }
        }
    }
    bfs.push_back({1, 1, 1});
    while(cnt){
        array<ll, 3> cur = bfs.back();
        bfs.pop_back();
        if(used[cur[0]][cur[1]]){continue;}
        // cout << cur[0] << ' ' << cur[1] << ' ' << cur[2] << endl;
        ans = cur[2];
        used[cur[0]][cur[1]] = 1;
        if(!(--cnt)){break;}
        for(array<ll, 2> d: dir){
            ll nx = cur[0] + d[0], ny = cur[1] + d[1];
            if(nx < 1 || nx > n || ny < 1 || ny > m){continue;}
            if(!used[nx][ny] && c[nx][ny] != '.'){
                if(c[nx][ny] == c[cur[0]][cur[1]]){
                    bfs.pb({nx, ny, cur[2]});
                }
                else{
                    bfs.push_front({nx, ny, cur[2] + 1});
                }
            }
        }
    }
    cout << ans << endl;


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

/*
4 4
RRRR
.F.R
.FFR
.RFR

*/

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