Submission #949952

#	Time	Username	Problem	Language	Result	Execution time	Memory
949952		chromatic	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	867 ms	148260 KiB

tracks

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_H=4000,MAX_W=4000;
bool visited[MAX_H][MAX_W];
char grid[MAX_H][MAX_W];
int dist[MAX_H][MAX_W];

//L,R,U,D
vector<int> dx={0,0,-1,1};
vector<int> dy={-1,1,0,0};

int main() {
    int h,w; cin >> h >> w;
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            cin >> grid[i][j];
        }
    }
    deque<pair<int,int>> q;
    dist[0][0]=1;
    q.push_back(make_pair(0,0));
    visited[0][0]=1;
    while(!q.empty()) {
        pair<int,int> v=q.front();
        q.pop_front();
        for(int i=0; i<4; i++) {
            pair<int,int> u={v.first+dx[i],v.second+dy[i]};
            if(u.first<0 || u.first>=h || u.second<0 || u.second>=w || visited[u.first][u.second] || grid[u.first][u.second]=='.') continue;
            if(grid[v.first][v.second]==grid[u.first][u.second]) {
                dist[u.first][u.second]=dist[v.first][v.second];
                q.push_front(make_pair(u.first,u.second));
                visited[u.first][u.second]=1;
            }
            else {
                dist[u.first][u.second]=dist[v.first][v.second]+1;
                q.push_back(make_pair(u.first,u.second));
                visited[u.first][u.second]=1;
            }
        }
    }
    int ans=0;
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            if(visited[i][j]) ans=max(ans,dist[i][j]);
        }
    }
    cout << ans;
    return 0;
}

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