Submission #920090

#	Time	Username	Problem	Language	Result	Execution time	Memory
920090		thienbao1602	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	691 ms	34412 KiB

tracks

#include    <bits/stdc++.h>
#define SKY
#define ll long long
#define ld long double
#define MASK(x) (1LL << x)
#define sz(x) (int)x.size()
#define ii pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set0(d) memset(d, 0, sizeof(d))
using namespace std;

const int LOG = 20;
const int base = 311;
const ll inf = 1e18;
const int block = 400;
const ll MOD = 1e9 + 7;
const int mxN = 1e6 + 66;
const int mxN2D = 4e3 + 55;
const int x[] = {0, 1, 0, -1};
const int y[] = {1, 0, -1, 0};

int H, W;
char grid[mxN2D][mxN2D];

bool safe(int x, int y)
{
    return (x >= 0 && x < H && y >= 0 && y < W);
}

void solve()
{
    cin >> H >> W;
    for (int r=0; r<H; r++)
    {
        for(int c=0; c<W; c++)
        {
            cin >> grid[r][c];
        }
    }

    char crossed_animal = grid[H - 1][W - 1];
    vector<vector<bool>> vis(H, vector<bool>(W, false));
    vis[H - 1][W - 1] = true;
    queue<ii> pq;
    pq.push(mp(H - 1, W - 1));

    bool other_animal = false;
    while(!pq.empty())
    {
        ii cell = pq.front();
        int u = cell.fi;
        int v = cell.se;

        for (int i=0; i<4; i++)
        {
            int ux = u + x[i];
            int vx = v + y[i];

            if (safe(ux, vx) && grid[ux][vx] != '.' && !vis[ux][vx])
            {
                if (crossed_animal != grid[ux][vx])
                {
                    other_animal = true;
                }
                pq.push(mp(ux, vx));
                vis[ux][vx] = true;
            }
        }
        pq.pop();
    }
    cout << 1 + other_animal;
}

int main()
{
    ios_base::sync_with_stdio(false);
    #ifdef SKY
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    #endif //SKY
    solve();
    return 0;
}

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