Submission #546492

#	Time	Username	Problem	Language	Result	Execution time	Memory
546492		_martynas	Tracks in the Snow (BOI13_tracks)	C++11	52.29 / 100	1187 ms	74284 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

using pii = pair<int, int>;

const int MXN = 4005;

int n, m;
int A[MXN][MXN];
int dirI[] = {0, 0, -1, 1};
int dirJ[] = {-1, 1, 0, 0};

bool inbounds(int i, int j)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char c; cin >> c;
            if(c == '.') A[i][j] = -1;
            else if(c == 'F') A[i][j] = 0;
            else A[i][j] = 1;
        }
    }

    queue<pii> Q[2];
    Q[0].push({0, 0});
    int which = 0;
    int cnt = 0;
    do {
        while(!Q[which].empty()) {
            int i = Q[which].front().F, j = Q[which].front().S;
            Q[which].pop();
            for(int k = 0; k < 4; k++) {
                int ii = i + dirI[k], jj = j + dirJ[k];
                if(inbounds(ii, jj)) {
                    if(A[ii][jj] == which) {
                        A[ii][jj] = -1;
                        Q[which].push({ii, jj});
                    }
                    else if(A[ii][jj] == 1-which) {
                        A[ii][jj] = -1;
                        Q[1-which].push({ii, jj});
                    }
                }
            }
        }
        which = 1-which;
        cnt++;
    } while(!Q[which].empty());

    cout << cnt;

    return 0;
}
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/

• Subtask 1: 21.666666666666668 / 30
• Subtask 2: 30.625 / 70