Submission #1316508

#TimeUsernameProblemLanguageResultExecution timeMemory
1316508vaderspaderTracks in the Snow (BOI13_tracks)C++20
2.19 / 100
366 ms141740 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll h, w;
    cin >> h >> w;

    vector<vector<char>> grid(h, vector<char>(w));
    rep(i, 0, h){
        rep(j, 0, w){
            cin >> grid[i][j];
        }
    }

    matrix visit(h, vi(w, 0));

    queue<pii> next;
    next.push({0, 0});

    while(!next.empty()){
        pii top = next.front();
        next.pop();
        ll x = top.first, y = top.second;

        if(visit[x][y]) continue;

        visit[x][y] = 1;

        if(x != h - 1){
            if(grid[x + 1][y] == grid[x][y]) next.push({x + 1, y});
        }
        if(y != w - 1){
            if(grid[x][y + 1] == grid[x][y]) next.push({x, y + 1});
        }
    }

    ll tot = 1;

    rep(i, 0, h){
        rep(j, 0, w){
            if(grid[i][j] == grid[0][0] && !visit[i][j]){
                tot++;
                break;
            }
        }
        if(tot > 1) break;
    }

    ll prev = tot;

    rep(i, 0, h){
        rep(j, 0, w){
            if(grid[i][j] != '.' && grid[i][j] != grid[0][0]){
                tot++;
                break;
            }
        }
        if(tot != prev) break;
    }

    cout << tot << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...