Submission #1269827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269827		liangjeremy	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	686 ms	208808 KiB

tracks

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    int h,w; cin>>h>>w; vector<vector<char>>a(h+1,vector<char>(w+1)); int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0};
    for(int i=1; i<=h; i++){
    	for(int j=1; j<=w; j++){
    		cin>>a[i][j];
    	}
    }
    auto check=[&](int x, int y){
    	if(x<1 || y<1 || x>h || y>w || a[x][y]=='.')return false;
    	return true; 
    };
    deque<pair<int,int>>dq; vector<vector<int>>dist(h+1,vector<int>(w+1,-1)); dq.push_back({1,1}); dist[1][1]=1; int ans=0; 
    while(dq.size()){
    	int x=dq.front().fi; int y=dq.front().se; dq.pop_front(); ans=max(ans,dist[x][y]); 
    	for(int i=0; i<4; i++){
    		int nx=x+dx[i]; int ny=y+dy[i];
    		if(check(nx,ny) && dist[nx][ny]==-1){
    			if(a[x][y]==a[nx][ny]){
    				dist[nx][ny]=dist[x][y]; dq.push_front({nx,ny}); 
    			}else{
    				dist[nx][ny]=dist[x][y]+1; dq.push_back({nx,ny}); 
    			}
    		}
    	}
    }
    cout<<ans<<'\n';
}
/*
O what can ail thee, knight-at-arms,
       Alone and palely loitering?
The sedge has withered from the lake,
       And no birds sing.
 
O what can ail thee, knight-at-arms,
       So haggard and so woe-begone?
The squirrel’s granary is full,
       And the harvest’s done.
 
I see a lily on thy brow,
       With anguish moist and fever-dew,
And on thy cheeks a fading rose
       Fast withereth too. 
*/

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