Submission #896676

#	Time	Username	Problem	Language	Result	Execution time	Memory
896676		Kodik	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	637 ms	116836 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef long long  ll;
typedef long double ld;
typedef short int shit;

#define ff first
#define ss second


bool check(int n, int m, int y, int x){
    return x>=0&&x<m&&y>=0&&y<n;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(NULL);
	// freopen("odometer.in", "r", stdin);
	// freopen("odometer.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> plain(n, vector<char>(m));
    vector<vector<int>> depth(n, vector<int>(m, 0));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> plain[i][j];
        }
    }
    int dy[] = {-1,0,1,0};
    int dx[] = {0,1,0,-1};
    int ans = 1;
    deque<pair<int,int>> dq;
    dq.push_back({0,0});
    depth[0][0] = 1;
    while (!dq.empty()){
        pair<int,int> coords = dq.front(); dq.pop_front();
        ans = max(ans, depth[coords.ff][coords.ss]);
        for(int i = 0; i < 4; ++i){
            int yy = coords.ff+dy[i];
            int xx = coords.ss+dx[i];
            if(check(n,m,yy,xx)){
                if(plain[yy][xx]!=plain[coords.ff][coords.ss]&plain[yy][xx]!='.'&&depth[yy][xx]==0){
                    dq.push_back({yy,xx});
                    depth[yy][xx] = depth[coords.ff][coords.ss] + 1;
                }else if(plain[yy][xx]==plain[coords.ff][coords.ss]&plain[yy][xx]!='.'&&depth[yy][xx]==0){
                    dq.push_front({yy,xx});
                    depth[yy][xx] = depth[coords.ff][coords.ss];
                }
            }
        }
    }
    cout << ans << '\n';
    return 0; 
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:42:33: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   42 |                 if(plain[yy][xx]!=plain[coords.ff][coords.ss]&plain[yy][xx]!='.'&&depth[yy][xx]==0){
tracks.cpp:45:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   45 |                 }else if(plain[yy][xx]==plain[coords.ff][coords.ss]&plain[yy][xx]!='.'&&depth[yy][xx]==0){

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