Submission #480361

#	Time	Username	Problem	Language	Result	Execution time	Memory
480361		nafis_shifat	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	827 ms	139052 KiB

tracks

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=4000+5;
const int inf=1e9;
char a[mxn][mxn];
int dist[mxn][mxn];
int vis[mxn][mxn];
int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};
int n, m ;

bool valid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= m; 
}
int main() {
    cin >> n >> m;


    for(int i = 1; i <= n; i++) {
        scanf("%s", a[i] + 1);
    }   
    memset(dist, -1, sizeof dist); 

    dist[1][1] = 1;

    deque<pii> q;

    q.push_back({1, 1});
    int ans = 1;

    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop_front();

        if(vis[i][j]) continue;


        ans = max(ans, dist[i][j]);

        for(int k = 0; k < 4; k++) {
            int ii = i + di[k];
            int jj = j + dj[k];

            if(!valid(ii, jj) || a[ii][jj] == '.') continue;

            int c = (a[ii][jj] != a[i][j]);

            if(dist[ii][jj] == -1 || dist[ii][jj] > dist[i][j] + c) {
                dist[ii][jj] = dist[i][j] + c;
                if(c) q.push_back({ii, jj});
                else q.push_front({ii, jj});
            }
        }
    }

    cout<<ans<<endl;


}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%s", a[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

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