Submission #875533

#	Time	Username	Problem	Language	Result	Execution time	Memory
875533		resting	Maze (JOI23_ho_t3)	C++17	100 / 100	713 ms	359800 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second

signed main(){
	int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1}; int dy[] = {0, 0, -1, 1, -1, 1, 1, -1};
	int n, r, c; cin >> r >> c >> n;
	int sr, sc; cin >> sr >> sc; sr--;sc--;
	int gr, gc; cin >> gr >> gc; gr--;gc--;
	vector<string> board(r);
	for(auto &s : board) cin >> s;
	vector<vector<int>> mark(r, vector<int>(c, 0));
	queue<pair<int,int>> todo;
	vector<pair<int,int>> funny;
	auto good = [&](pair<int,int>p){
		return p.ff>=0&&p.ss>=0&&p.ff< r&&p.ss<c;
	};
	auto ad = [&](pair<int,int> p){
		if(mark[p.ff][p.ss]) return;
		if(board[p.ff][p.ss]=='#'){
			funny.push_back(p);
			return;
		}
		mark[p.ff][p.ss] = 1;
		for(int d = 0; d < 4; d++){
			auto t = p; t.ff+=dx[d]; t.ss+=dy[d];
			if(good(t)) todo.push(t);
		}
	};
	auto ad2 = [&](pair<int,int> p){
		if(mark[p.ff][p.ss]) return;
		mark[p.ff][p.ss] = 1;
		for(int d = 0; d < 8; d++){
			auto t = p; t.ff+=dx[d]; t.ss+=dy[d];
			if(good(t)) {
				if(d<4)
				todo.push(t);
				funny.push_back(t);
			}
		}
	};
	ad({sr, sc});
	int res = 0;
	for(;;){
		while(!todo.empty()){
			ad(todo.front()); 
			todo.pop();
		}
		if(mark[gr][gc]) break;
		res++;
		//do funny thing
		for(int i = 0; i < n; i++){
			auto tmp = funny; funny.clear();
			for(auto &x : tmp){
				ad2(x);
			}
		}funny.clear();

	}
	cout<<res<<endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6