제출 #1160155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160155		sgonur	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	2105 ms	470644 KiB

tracks

#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;

pair<int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main()
{
    int h, w;
    cin >> h >> w;

    char meadow[h][w];
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;

        for (int j = 0; j < w; j++) meadow[i][j] = s[j];
    }

    deque<pair<int, int>> q;
    q.push_front({0, 0});

    map<pair<int, int>, int> dist;
    dist[{0, 0}] = 0;

    int ans = 1;
    while (!q.empty())
    {
        int i = q.front().first, j = q.front().second;
        q.pop_front();

        ans = max(ans, dist[{i, j}]);

        for (auto &p : dir)
        {
            int inew = i + p.first, jnew = j + p.second;

            if (inew < 0 || jnew < 0 || inew >= h || jnew >= w) continue;
            if (dist.count({inew, jnew})) continue;


            if (meadow[i][j] == meadow[inew][jnew])
            {
                q.push_front({inew, jnew});
                dist[{inew, jnew}] = dist[{i, j}];
            }
            else
            {
                q.push_back({inew, jnew});
                dist[{inew, jnew}] = dist[{i, j}] + 1;
            }
        }
    }

    cout << ans;
}

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