Submission #1115081

#TimeUsernameProblemLanguageResultExecution timeMemory
1115081DON_FTracks in the Snow (BOI13_tracks)C++14
100 / 100
401 ms89996 KiB
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 4e3 + 7, Mx = 1e9 + 9;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m;
string s[N];
bool vis[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    L(i, 0, n){
        cin >> s[i];
    }
    auto in = [&](int x, int y){
        return (x >= 0 && y >= 0 && x < n && y < m);
    };
    int ans = 1;
    char lst = s[0][0];
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    vis[0][0] = true;
    while (!dq.empty()){
        pair<int, int> t = dq.front();
        dq.pop_front();
        if (s[t.first][t.second] != lst){
            lst = s[t.first][t.second];
            ++ans;
        }
        L(i, 0, 4){
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if (in(nx, ny) && vis[nx][ny] == false && s[nx][ny] != '.'){
                if (s[nx][ny] == s[t.first][t.second])dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
                vis[nx][ny] = true;
            }
        }
    }
    cout << ans;
}



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