Submission #540673

#	Time	Username	Problem	Language	Result	Execution time	Memory
540673		Ekkorash	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1783 ms	124312 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
using namespace std;

int main() {
	int H, W;
	std::cin >> H >> W;
	
	std::vector<std::vector<bool>> v(H, std::vector<bool>(W));
	v[0][0] = true;
	std::vector<std::vector<char>> g(H, std::vector<char>(W));
	std::vector<std::vector<int>> path(H, std::vector<int>(W));
	path[0][0] = 1;
	
	for (int i = 0; i < H; ++i) {
	    for (int j = 0; j < W; ++j) {
	        std::cin >> g[i][j];
	    }
	}
	
	std::deque<std::pair<int, int>> deq;
	deq.push_front({0, 0});
	
	int ans = 0;
	while(!deq.empty()) {
	    std::pair<int, int> cur_node = deq.front();
	    deq.pop_front();
	    ans = std::max(ans, path[cur_node.first][cur_node.second]);
	    
	    auto func = [&](std::pair<int, int> visit_node) {
	        if (visit_node.first >= 0 && visit_node.first < H && 
	            visit_node.second >= 0 && visit_node.second < W &&
	            g[visit_node.first][visit_node.second] != '.' && 
	            !v[visit_node.first][visit_node.second])
    	    {
    	        v[visit_node.first][visit_node.second] = true;
    	        if (g[visit_node.first][visit_node.second] == g[cur_node.first][cur_node.second])
    	        {
    	            deq.push_front({visit_node.first, visit_node.second});
    	            path[visit_node.first][visit_node.second] = path[cur_node.first][cur_node.second];
    	        } else {
    	            deq.push_back({visit_node.first, visit_node.second});
    	            path[visit_node.first][visit_node.second] = path[cur_node.first][cur_node.second] + 1;
    	        }
    	    }
	    };
	    
	    func({cur_node.first - 1, cur_node.second});
	    func({cur_node.first + 1, cur_node.second});
	    func({cur_node.first, cur_node.second + 1});
	    func({cur_node.first, cur_node.second - 1});
	}
	
	std::cout << ans << "\n";
	
	return 0;
}

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