Submission #407097

#	Time	Username	Problem	Language	Result	Execution time	Memory
407097		iulia13	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	534 ms	1048580 KiB

tracks

#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
const int N = 4005;
vector <int> g[N * N];
char a[N][N];
int b[N][N];
int viz[N * N];
int lvl[N * N];
int cnt, ans = 0;
int dL[4] = {0, 1, 0, -1};
int dC[4] = {1, 0, -1, 0};
void filll(int x, int y, char car)
{
    b[x][y] = cnt;
    for (int i = 0; i < 4; i++)
    {
int        xx = x + dL[i];
int        yy = y + dC[i];
        if (a[xx][yy] == car && !b[xx][yy])
            filll(xx, yy, car);
    }
}
map <int, int> mp[N * N];
queue <int> q;
int main()
{
    int n, m, i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        cin >> a[i] + 1;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (b[i][j] || a[i][j] == '.')
                continue;
            cnt++;
            filll(i, j, a[i][j]);
        }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            for (int h = 0; h < 4; h++)
            {
                int x = i + dL[h];
                int y = j + dC[h];
                if (b[x][y] != b[i][j] && b[x][y] && b[i][j])
                {
                    mp[b[i][j]][b[x][y]] =  1;
                    mp[b[x][y]][b[i][j]] =  1;
                }
            }
        }
    for (i = 1; i <= cnt; i++)
        for (auto jj : mp[i])
            g[i].push_back(jj.first);
    q.push(1);
    lvl[1] = 1;
    viz[1] = 1;

    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (auto y : g[x])
        {
            if (viz[y])
                continue;
            viz[y] = 1;
            q.push(y);
            lvl[y] = lvl[x] + 1;
            ans = max(ans, lvl[y]);
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         cin >> a[i] + 1;
      |                ~~~~~^~~

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