제출 #523071

#제출 시각아이디문제언어결과실행 시간메모리
523071Hamed5001Tracks in the Snow (BOI13_tracks)C++14
2.19 / 100
1139 ms806796 KiB
#include <bits/stdc++.h>
using namespace std;

const int mxN = 4000;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
char G[mxN][mxN];
bool vis[mxN][mxN];
int N, M;

bool valid(int i, int j) {
    return 0 <= i && i < N && 0 <= j && j < M;
}

void dfs(int i, int j, bool which) {
    if (vis[i][j]) return;
    vis[i][j] = 1;
    for (int d = 0; d < 4; ++d)
        if (valid(i + di[d], j + dj[d]) && (G[i + di[d]][j + dj[d]] == 'R') == which)
            dfs(i + di[d], j + dj[d], which);
}

void solve() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> G[i][j];
    
    bool dis[2] = {};
    dfs(0, 0, G[0][0] == 'R');
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (G[i][j] == '.' || vis[i][j]) continue; 
            bool which = (G[i][j] == 'R');
            dis[which] = 1;
            dfs(i, j, which);
        }
    }
    cout << 1 + dis[0] + dis[1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...