제출 #340194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340194		blue	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	859 ms	103524 KiB

tracks

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

/*
Consider each connected component as one node in the graph.
Consider adjacent connected components as having an edge between them
Res = max distance between cc(1, 1) and any other cc
*/

int H, W;

int p(int i, int j)
{
    return (W+2)*i + j;
}

int main()
{
    cin >> H >> W;

    char c[(H+2)*(W+2)];
    for(int i = 0; i <= H; i++) c[p(i, 0)] = c[p(i, W+1)] = '.';
    for(int j = 0; j <= W; j++) c[p(0, j)] = c[p(H+1, j)] = '.';
    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            cin >> c[p(i, j)];
        }
    }

    int temp;
    vector<int> res((H+2)*(W+2), 1e9);
    res[p(1, 1)] = 0;

    deque<int> tbv;
    tbv.push_back(p(1, 1));

    int final_res = 0;

    while(!tbv.empty())
    {
        temp = tbv.front();
        tbv.pop_front();
        final_res = max(final_res, res[temp]);

        for(int k: {temp+1, temp-1, temp+W+2, temp-W-2})
        {
            if(c[k] == '.') continue;
            if(res[k] != 1e9) continue;
            if(c[temp] != c[k])
            {
                res[k] = res[temp] + 1;
                tbv.push_back(k);
            }
            else
            {
                res[k] = res[temp];
                tbv.push_front(k);
            }
        }
    }

    cout << final_res + 1 << '\n';
}

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