Submission #388295

#	Time	Username	Problem	Language	Result	Execution time	Memory
388295		Monchito	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1458 ms	101784 KiB

tracks

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
using ii = pair<int,int>;

int xd[] = {1,-1,0,0}, yd[] = {0,0,1,-1};

#define forn(i, x, n) for(int i = (x); i < (int)(n); i++)

const int MAXS = 4000;
int N, M;
char G[MAXS][MAXS];

bool inside(int i, int j){
    return (i > -1 && j > -1 && i < N && j < M && G[i][j] != '.'); 
}

int main(){
    scanf("%d%d",&N,&M); 
    forn(i,0,N) forn(j,0,M) scanf(" %c",&G[i][j]);

    deque<pair<ii, int>> Q;
    vector<vector<bool>> vis(N, vector<bool>(M, false));
    int ans=0;

    Q.push_front({{0,0},1});

    while(!Q.empty()){
        pair<ii, int> p = Q.front(); Q.pop_front();
        int d = p.second; ii pos = p.first;

        ans = max(ans, d);

        forn(i,0,4){
            int x2 = xd[i]+pos.first, y2 = yd[i]+pos.second;
            if(inside(x2, y2) && !vis[x2][y2]){
                vis[x2][y2] = true;
                if(G[pos.first][pos.second] == G[x2][y2]) Q.push_front({{x2,y2},d});
                else Q.push_back({{x2,y2},d+1});
            }
        }
    }

    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     forn(i,0,N) forn(j,0,M) scanf(" %c",&G[i][j]);
      |                             ~~~~~^~~~~~~~~~~~~~~~

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