Submission #1092212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092212		brinton	Tracks in the Snow (BOI13_tracks)	C++14	46.77 / 100	2092 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int H,W;
void dfs(int r,int c,vector<vector<int>>& matrix,vector<vector<int>>& minDist){
	// cout << r << " " << c << endl;
	int dx[4] = {0,1,-1,0};
	int dy[4] = {1,0,0,-1};
	for(int i = 0;i < 4;i++){
		int newX = r+dx[i];
		int newY = c+dy[i];
		if(newX < 0 || newY < 0 || newX >= H || newY >= W){
			continue;
		}
		if(matrix[newX][newY] == 0)continue;
		int newDist = minDist[r][c];
		if(matrix[newX][newY] != matrix[r][c]){
			newDist++;
		}
		if(minDist[newX][newY] > newDist){
			minDist[newX][newY] = newDist;
			dfs(newX,newY,matrix,minDist);
		}
	}
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    
    cin >> H >> W;
    vector<vector<int>> matrix(H,vector<int>(W,0));
    
    for(int i = 0;i < H;i++){
    	for(int j = 0; j < W;j++){
    		char tmp;
    		cin >> tmp;
    		if(tmp == 'F'){
    			matrix[i][j] = 1;
    		}else if(tmp == 'R'){
    			matrix[i][j] = 2;
    		}
    	}
    }
    vector<vector<int>> min_dist(H,vector<int>(W,INT_MAX));
    int ans = 0;
    min_dist[0][0] = 1;
    dfs(0,0,matrix,min_dist);
    for(int i = 0; i < H;i++){
    	for(int j = 0; j < W;j++){
    		if(matrix[i][j] != 0){
    			ans = max(min_dist[i][j],ans);
    			// cout << min_dist[i][j] << " ";
    		}
    		// else{
    			// cout << 0 << " ";
    		// }
    	}
    	// cout << endl;
    }
    cout << ans;
}

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