Submission #1015789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015789		KALARRY	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	806 ms	120964 KiB

tracks

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int H,W,di[4] = {1,-1,0,0},dj[4] = {0,0,1,-1},dist[4005][4005];
char grid[4005][4005];

bool is_ok(int i,int j)
{
    if(i >= 1 && i <= H && j >= 1 && j <= W && grid[i][j] != '.')
        return true;
    return false;
}

void BFS(int starti,int startj)
{
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            if(grid[i][j]!='.')
                dist[i][j] = INF;
    deque<pair<int,int>> q;
    dist[starti][startj] = 1;
    q.push_back({starti,startj});
    while(!q.empty())
    {
        pair<int,int> v = q.front();
        int i = v.first;
        int j = v.second;
        q.pop_front();
        for(int k = 0 ; k <= 3 ; k++)
        {
            int new_i = i + di[k];
            int new_j = j + dj[k];
            if(is_ok(new_i,new_j))
            {
                if(grid[i][j]==grid[new_i][new_j])
                {
                    if(dist[i][j] < dist[new_i][new_j])
                    {
                        dist[new_i][new_j] = dist[i][j];
                        q.push_front({new_i,new_j});
                    }
                }
                else
                {
                    if(dist[i][j] + 1 < dist[new_i][new_j])
                    {
                        dist[new_i][new_j] = dist[i][j] + 1;
                        q.push_back({new_i,new_j});
                    }
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d",&H,&W);
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            scanf(" %c",&grid[i][j]);
    BFS(1,1);
    int ans = 0;
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            ans = max(ans,dist[i][j]);
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d%d",&H,&W);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf(" %c",&grid[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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