Submission #538688

#	Time	Username	Problem	Language	Result	Execution time	Memory
538688		Lobo	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1064 ms	45868 KiB

tracks

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 4400

ii n, m;
char c[maxn][maxn];
ii dx[4] = {0,0,1,-1};
ii dy[4] = {1,-1,0,0};

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

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> m;

    for(ii i = 1; i <= n; i++) {
        c[i][0] = c[i][m+1] = '.';
        string s;
        cin >> s;
        for(ii j = 1; j <= m; j++) {
            c[i][j] = s[j-1];
        }
    }

    for(ii j = 1; j <= m; j++) c[0][j] = c[n+1][j] = '.';

    queue<pair<ii,ii>> q1, q2;
    ii ans = 0;
    q2.push(mp(1,1));
    while(q1.size() + q2.size()) {
        if(q1.empty()) {
            ans++;
            swap(q1,q2);
        }

        ii x = q1.front().fr;
        ii y = q1.front().sc;
        q1.pop();
        if(c[x][y] == '.') continue;

        for(ii i = 0; i < 4; i++) {
            ii x1 = x + dx[i];
            ii y1 = y + dy[i];

            if(c[x1][y1] == c[x][y]) {
                q1.push(mp(x1,y1));
            }
            else if(c[x1][y1] != '.') {
                q2.push(mp(x1,y1));
            }
        }
        c[x][y] = '.';
    }

    cout << ans << endl;

}

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