Submission #683869

#	Time	Username	Problem	Language	Result	Execution time	Memory
683869		BEMWA	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	862 ms	119484 KiB

tracks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
  //cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;

        int dist[n][m];
        char grid[n][m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> grid[i][j];
                dist[i][j] = INT_MAX;
            }
        }   

        int ans = 0;
        

        deque<pair<int,int>> q;
        q.push_front({0, 0});
        dist[0][0] = 0;

        while(!q.empty()){
            pair<int,int> cur = q.front();
            q.pop_front();

            ans = max(ans, dist[cur.first][cur.second] + 1);

            for(int k = 0; k < 4; k++){
                int nx = dx[k] + cur.first;
                int ny = dy[k] + cur.second;
                
                if(!(nx >= 0 and nx < n and ny >= 0 and ny < m))continue;
                if(grid[nx][ny] == '.')continue;

                if(grid[nx][ny] != grid[cur.first][cur.second] and dist[nx][ny] > dist[cur.first][cur.second] + 1){
                    dist[nx][ny] = dist[cur.first][cur.second] + 1;
                    q.push_back({nx, ny});
                }else if(grid[nx][ny] == grid[cur.first][cur.second] and dist[nx][ny] > dist[cur.first][cur.second]){
                    dist[nx][ny] = dist[cur.first][cur.second];
                    q.push_front({nx, ny});
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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