Submission #786053

#	Time	Username	Problem	Language	Result	Execution time	Memory
786053		orcslop	Tracks in the Snow (BOI13_tracks)	C++17	32.19 / 100	25 ms	3124 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 505; 
const int dx[4] = {-1, 1, 0, 0}; 
const int dy[4] = {0, 0, -1, 1}; 

int n, m; 
char snow[MAXN][MAXN]; 
int depth[MAXN][MAXN]; 
deque<pair<int, int>> dq; 

bool inbounds(int x, int y){
    return (x >= 0 && y >= 0 && x < n && y < m && snow[x][y] != '.'); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> snow[i][j]; 
        }
    }
    depth[0][0] = 1; 
    dq.push_back(make_pair(0, 0)); 
    int ans = 0; 

    while(!dq.empty()){
        pair<int, int> curr = dq.front(); 
        dq.pop_front(); 
        ans = max(ans, depth[curr.first][curr.second]); 

        for(int i = 0; i < 4; i++){
            int x = curr.first + dx[i]; 
            int y = curr.second + dy[i]; 
            if(inbounds(x, y) && !depth[x][y]){
                if(snow[x][y] == snow[curr.first][curr.second]){
                    depth[x][y] = depth[curr.first][curr.second]; 
                    dq.push_front(make_pair(x, y)); 
                }
                else{
                    depth[x][y] = depth[curr.first][curr.second] + 1; 
                    dq.push_back(make_pair(x, y)); 
                }
            }
        }
    }

    cout << ans << '\n'; 
    return 0; 
}

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