Submission #523071

#	Time	Username	Problem	Language	Result	Execution time	Memory
523071		Hamed5001	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	1139 ms	806796 KiB

tracks

#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;
}

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