제출 #883769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883769		Billy_Nguyen	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	627 ms	220932 KiB

tracks

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

#define x first
#define fastio()                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also
                               // the number has to be in long long otherwise
                               // if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
ll H, W;
vector<vector<char>> grid;
vector<vector<ll>> depths;

void solve()
{
    cin >> H >> W;
    grid.resize(H + 1);
    depths.resize(H + 1);

    REP(i, 0, H + 1)
    {
        grid[i].resize(W + 1);
        depths[i].resize(W + 1, 0);
    }

    REP(i, 1, H + 1)
    {
        REP(j, 1, W + 1)
        {
            cin >> grid[i][j];
        }
    }

    deque<pair<ll, ll>> q;
    depths[1][1] = 1;
    q.push_back({1, 1});
    ll ans = 0;

    while (!q.empty())
    {
        pair<ll, ll> curr = q.front();
        q.pop_front();

        ans = max(ans, depths[curr.x][curr.y]);

        REP(k, 0, 4)
        {
            if (curr.x + dy[k] < 1 || curr.y + dx[k] < 1 ||
                curr.x + dy[k] > H || curr.y + dx[k] > W)
            {
                continue;
            }

            pair<ll, ll> nxt = {curr.x + dy[k], curr.y + dx[k]};

            if (grid[nxt.x][nxt.y] == '.')
            {
                continue;
            }

            if (depths[nxt.x][nxt.y] != 0)
            {
                continue;
            }

            if (grid[nxt.x][nxt.y] == grid[curr.x][curr.y])
            {
                    depths[nxt.x][nxt.y] = depths[curr.x][curr.y];
                    q.push_front(nxt);
            }
            else
            {
                    depths[nxt.x][nxt.y] = depths[curr.x][curr.y] + 1;
                    q.push_back(nxt);
            }
        }
    }

    cout << ans << "\n";
}

int main()
{
    fastio();
    solve();

    return 0;
}

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