Submission #1072617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072617		redLotus31415	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1042 ms	122288 KiB

tracks

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <fstream>
#include <string>
#include <bits/stdc++.h>
#include <deque> 
#include <numeric>
using namespace std;

#define FOR(i,L,R) for (int i = L; i < R; i++) 
#define FOR_STEP(i,L,R, STEP) for (int i = L; i < R; i+= STEP)

struct coord {
    int x;
    int y;
}; 

int main(){
    int H, W;
    cin >> H >> W; 
    char array[H][W]; 
    int d[H][W]; 
    // use '.' as visited
    FOR(i, 0, H) {
        FOR(j, 0, W) {
            char x; cin >> x; 
            array[i][j] = x; 
            d[i][j] = INT_MAX; 
        }
    }

    

    int left[] = {-1, 1, 0, 0};
    int right[] = {0, 0, -1, 1}; 


    deque<coord> bfs_queue; 
    bfs_queue.push_front({0, 0});
    d[0][0] = 0; 
    while (!bfs_queue.empty()) {
        coord topCoord = bfs_queue.front();
        bfs_queue.pop_front(); 
        FOR (i, 0, 4) {
            int nx = topCoord.x + left[i]; 
            int ny = topCoord.y + right[i]; 
            if (nx >=0 && nx < H && ny <W && ny >= 0) {
                if (array[nx][ny] != '.') {
                    if (array[nx][ny] == array[topCoord.x][topCoord.y] && d[topCoord.x][topCoord.y] < d[nx][ny]) {
                        bfs_queue.push_front({nx, ny});
                        d[nx][ny] = d[topCoord.x][topCoord.y];
                    } else if (array[nx][ny] != array[topCoord.x][topCoord.y] && d[topCoord.x][topCoord.y] + 1 < d[nx][ny]){
                        bfs_queue.push_back({nx, ny});
                        d[nx][ny] = d[topCoord.x][topCoord.y] + 1;
                    }
                }
            }
        }
        array[topCoord.x][topCoord.y] = '.'; 
    }
    int maxDepth = 0; 
    FOR (i, 0, H) {
        FOR (j, 0, W) {
            if (d[i][j] != INT_MAX && d[i][j] > maxDepth) {
                maxDepth = d[i][j];
            }
        } 
    }

    cout << maxDepth + 1; 
    

}

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