Submission #948132

#	Time	Username	Problem	Language	Result	Execution time	Memory
948132		akkshaysr	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	685 ms	174884 KiB

tracks

#include <bits/stdc++.h>
#define fr first
#define se second
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define repr(i,a,b) for(int i = a; i > (b); --i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IN(i,l,r) (l<i&&i<r)
#define pb push_back
#define dbg(v) \
	cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef long long ll;
int h,w;
const int U = 4002;
int grid[U][U],dist[U][U];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

bool valid(int x,int y){
    return IN(x,-1,h) && IN(y,-1,w) && grid[x][y]!=1;
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
    cin >> h >> w;
    rep(i,0,h){
        rep(j,0,w){
            char x; cin >> x;
            if(x=='.') grid[i][j]=1; 
            else if(x=='F') grid[i][j]=2; 
            else if(x=='R') grid[i][j]=3; 
        }
    }
    deque<pair<int,int>> q;
    q.push_back({0,0});
    dist[0][0] = 1;
    while(q.size()){
        pi c = q.front(); q.pop_front();
        rep(k,0,4){
            int x = c.fr+dx[k],y = c.se+dy[k];
            if(valid(x,y) && dist[x][y] == 0){
                if(grid[x][y] == grid[c.fr][c.se]){
                    dist[x][y] = dist[c.fr][c.se];
                    q.push_front({x,y});
                }else{
                    dist[x][y] = dist[c.fr][c.se]+1;
                    q.push_back({x,y});
                }
            }
        }
    }
    int ans = 1;
    rep(i,0,h)
        rep(j,0,w)  ans = max(ans,dist[i][j]);
    cout << ans << '\n';
}

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