제출 #1127093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127093		ALTAKEXE	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1376 ms	174064 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int N = 4e3 + 5;
using namespace std;
char snow[N][N];
int dist[N][N], vis[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int w, h;
bool check(int x, int y)
{
    return (1 <= x && x <= w) && (1 <= y && y <= h);
}
int main()
{
    cin >> h >> w;
    for (int y = 1; y <= h; y++)
    {
        for (int x = 1; x <= w; x++)
        {
            cin >> snow[x][y];
        }
    }

    deque<pair<int, int>> dq;
    dq.push_front({1, 1});
    dist[1][1] = 1;
    vis[1][1] = true;
    int ans = 1;

    while (!dq.empty())
    {
        int x = dq.front().ff, y = dq.front().ss;
        dq.pop_front();
        ans = max(ans, dist[x][y]);
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];

            if (!check(xx, yy))
                continue;
            if (snow[xx][yy] == '.')
                continue;
            if (vis[xx][yy])
                continue;

            vis[xx][yy] = true;

            if (snow[x][y] == snow[xx][yy])
            {
                dist[xx][yy] = dist[x][y];
                dq.push_front({xx, yy});
            }
            else
            {
                dist[xx][yy] = dist[x][y] + 1;
                dq.push_back({xx, yy});
            }
        }
    }
    cout << ans << endl;
}

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