Submission #493783

#	Time	Username	Problem	Language	Result	Execution time	Memory
493783		goodluck2020	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	827 ms	175916 KiB

tracks

#include <bits/stdc++.h>
#define task "tracks"

using namespace std;
const int N = 4e3 + 5;
int n, m, dist[N][N], Visited[N][N], ans(0);
char A[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool inside(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m) return 0;
    return 1;
}
struct Data
{
    int x, y;
};
deque < Data > dq;
void BFS01()
{
    dq.push_back({1, 1}); Visited[1][1] = 1; dist[1][1] = 1;
    while(!dq.empty())
    {
        int x = dq.front().x;
        int y = dq.front().y;
        dq.pop_front();
        for(int i = 0; i < 4; i++)
        {
            int u = x + dx[i];
            int v = y + dy[i];
            if(inside(u, v) && !Visited[u][v] && A[u][v] != '.')
            {
                if(A[u][v] == A[x][y])
                {
                    dq.push_front({u, v});
                    dist[u][v] = dist[x][y];
                    Visited[u][v] = 1;
                }
                else
                {
                    dq.push_back({u, v});
                    dist[u][v] = dist[x][y] + 1;
                    Visited[u][v] = 1;
                }
            }
        }
    }
}
int main()
{
    if(fopen(task ".inp","r"))
    {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) cin >> A[i][j];
    BFS01();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        ans = max(ans, dist[i][j]);
    cout << ans;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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