Submission #134498

#	Time	Username	Problem	Language	Result	Execution time	Memory
134498		wzy	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	863 ms	118916 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp mka
string s[4005];
int dist[4005][4005];
deque<pair<int, int> > dq;
int h , w;
int dx[4] = { 0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	cin>>h>>w;
	for(int i = 0 ; i < h ; i ++){
		cin>>s[i];
		for(int j = 0 ; j  < w ; j ++){
			dist[i][j] = numeric_limits<int>::max() ;
			dist[i][j]--;
		}
	}
	dq.push_back(pair<int,int>(0,0));
	int ans = 0;
	dist[0][0] = 0;
	while(!dq.empty()){
		pii u = dq.front();
		ans = max(ans , dist[u.first][u.second]+1);
		dq.pop_front();
		for(int i = 0 ; i < 4 ; i++){
			int x = u.first + dx[i] , y = u.second + dy[i];
			if(x >= 0 && y >= 0 && x < h && y < w){
				if(s[x][y] != s[u.first][u.second] && s[x][y] != '.' && dist[x][y] > (dist[u.first][u.second] + 1)){
					dist[x][y] = dist[u.first][u.second] + 1;
					dq.push_back(pair<int,int>(x,y));
				}
				else{
					if(s[x][y] == s[u.first][u.second] && dist[x][y] > (dist[u.first][u.second])){
						dist[x][y] = dist[u.first][u.second];
						dq.push_front(pair<int,int>(x,y));
					}
				}
			}
		}
	}
	cout<<ans<<"\n";
}

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