제출 #920118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920118		thienbao1602	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	739 ms	164136 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 && grid[x][y] != '.');
}

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

    deque<ii> pq;
    pq.push_back(mp(0, 0));
    vector<vector<int>> depth(H, vector<int>(W, 0));
    depth[0][0] = 1;

    int ans = 1;
    while(!pq.empty())
    {
        ii cell = pq.front();
        pq.pop_front();
        int u = cell.fi;
        int v = cell.se;

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

            if (safe(ux, vx) && !depth[ux][vx])
            {
                depth[ux][vx] = depth[u][v] + (grid[ux][vx] != grid[u][v]);
                if (grid[ux][vx] == grid[u][v])
                {
                    pq.push_front(mp(ux, vx));
                } else
                {
                    pq.push_back(mp(ux, vx));
                }
            }
        }
    }
    cout << ans;
}

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: 30 / 30
• Subtask 2: 70 / 70