Submission #372533

#	Time	Username	Problem	Language	Result	Execution time	Memory
372533		ml1234	Tracks in the Snow (BOI13_tracks)	C++17	22.60 / 100	559 ms	206268 KiB

tracks

#include <iostream>
#include <deque>
using namespace std;
bool check(int x, int y);

int h, w;
string snow[4000];
int main() 
{
    cin >> h >> w;
    for (int i = 0; i < h; i++)
    {
        cin >> snow[i];
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    int depth[h][w];
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            depth[i][j] = 0;
        }
    }
    depth[0][0] = 1;
    int ans = 1;
    int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
    while (!q.empty())
    {
        pair<int, int> curr = q.front();
        q.pop_front();
        ans = max(ans, depth[curr.first][curr.second]);
        for (int i = 0; i < 4; i++)
        {
            int x = curr.first + dx[i], y = curr.second + dy[i];
            if (depth[x][y] == 0 && check(x, y))
            {
                if (snow[x][y] == snow[curr.first][curr.second])
                {
                    q.push_front({x, y});
                    depth[x][y] = depth[curr.first][curr.second];
                }
                else
                {
                    q.push_back({x, y});
                    depth[x][y] = depth[curr.first][curr.second] + 1;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

bool check(int x, int y)
{
    return x >= 0 && x < h && y >= 0 && y < w && snow[x][y] != '.';
}

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