제출 #743738

#제출 시각아이디문제언어결과실행 시간메모리
743738Azm1tTracks in the Snow (BOI13_tracks)C++17
24.06 / 100
659 ms162328 KiB
#include "bits/stdc++.h"
using namespace std;
#define forn for (int i = 0; i < n; i++)
#define int long long
#define ed "\n"
#define cyes cout << "YES\n"
#define cno cout << "NO\n"
#define pb push_back
#define deb cout << "Hi\n"
#define pint pair<int, int>
const long long MOD = 1000000007;

void dbg_out(){cerr<<"\n";}
template<typename Head,typename... Tail>
void dbg_out(Head H,Tail... T){cerr<<' '<<H;dbg_out(T...);}
#define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dbg_out(__VA_ARGS__)

//-------------------------------------------------------------------------------------------------------------------------------------------------------------------//


int32_t main(){

    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m; cin>>n>>m;
    char a[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0 ; j < m; j++){
            cin>>a[i][j];
        }
    }

    char cur = a[0][0];
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    deque<pair<pint, char>> d;
    d.pb({{0, 0}, cur});

    auto valid = [&](int i, int j){
        return(i < n && i >= 0 && j < m && j >= 0);
    };

    vector<pint> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int ans = 1;
    // int t = 0;

    while(!d.empty()){
        // cout << ++t << ed;
        auto c = d.front();
        d.pop_front();
        int i = c.first.first;
        int j = c.first.second;
        char x = c.second;
        if(x != cur){
            cur = x;
            ans++;
        }

        for(auto val: moves){
            int nx = i + val.first;
            int ny = j + val.second;
            char y;
            if(x == 'F') y = 'R';
            else y = 'F';
            if(valid(nx, ny) && !vis[nx][ny] && a[nx][ny] != '.'){
                if(x == a[nx][ny]) d.push_front({{nx, ny}, x});
                else d.push_back({{nx, ny}, y});
                vis[nx][ny] = true;
            }  
        }
        

    }
    srand(time(0));
    cout << ans + rand()%2 << ed;

    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...