Submission #860524

#	Time	Username	Problem	Language	Result	Execution time	Memory
860524		NotLinux	Maze (JOI23_ho_t3)	C++17	86 / 100	2064 ms	308720 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void solve(){
	int r,c,n;
	cin >> r >> c >> n;	
	pair < int , int > s,g;
	cin >> s.first >> s.second >> g.first >> g.second;
	s.first--;s.second--;g.first--;g.second--;
	int grid[r][c];
	set < int > hor[r] , ver[c];
	for(int i = 0;i<r;i++){//1 = # , 0 = .
		string str;cin >> str;
		for(int j = 0;j<c;j++){
			grid[i][j] = str[j] == '#';
			if(i != s.first or j != s.second){
				ver[j].insert(i);
				hor[i].insert(j);
			}
		}
	}
	priority_queue < pair < int , pair < int , int > > > bfs;//{dist,{x,y}}
	bfs.push({0,s});
	int vis[r][c];
	memset(vis , 0 , sizeof(vis));
	while(bfs.size()){
		pair < int , int > p = bfs.top().second;
		int dist = -bfs.top().first;
		bfs.pop();
		if(vis[p.first][p.second])continue;
		//cout << "bfs : " << p.first << " " << p.second << " " << dist << endl;
		vis[p.first][p.second] = 1;
		if(p == g){
			cout << dist << '\n';
			return;
		}
		//spread
		if((p.first+n) < r){//	({n,-n} , {n,n})
			auto lb = hor[p.first + n].upper_bound(p.second - n);
			auto ub = hor[p.first + n].lower_bound(p.second + n);
			if(lb != hor[p.first + n].end() and ub != hor[p.first + n].begin()){
				vector < int > willdel;
				for(auto it = lb;it != ub;++it){
					willdel.push_back(*it);
				}
				for(auto itr : willdel){
					bfs.push({-dist-1,{p.first + n , itr}});
					hor[p.first + n].extract(itr);
					ver[itr].extract(p.first + n);
				}
			}
		}
		if((p.first - n) >= 0){//	({-n,-n} , {-n,n})
			auto lb = hor[p.first - n].upper_bound(p.second - n);
			auto ub = hor[p.first - n].lower_bound(p.second + n);
			if(lb != hor[p.first - n].end() and ub != hor[p.first - n].begin()){
				vector < int > willdel;
				for(auto it = lb;it != ub;++it){
					willdel.push_back(*it);
				}
				for(auto itr : willdel){
					bfs.push({-dist-1,{p.first - n , itr}});
					hor[p.first - n].extract(itr);
					ver[itr].extract(p.first - n);
				}
			}
		}
		if((p.second + n) < c){//	({-n,n} , {n,n})
			auto lb = ver[p.second + n].upper_bound(p.first - n);
			auto ub = ver[p.second + n].lower_bound(p.first + n);
			if(lb != ver[p.second + n].end() and ub != ver[p.second + n].begin()){
				vector < int > willdel;
				for(auto it = lb;it != ub;++it){
					willdel.push_back(*it);
				}
				for(auto itr : willdel){
					bfs.push({-dist-1,{itr , p.second + n,}});
					ver[p.second + n].extract(itr);
					hor[itr].extract(p.second + n);
				}
			}
		}
		if((p.second - n) >= 0){//	({-n,-n} , {n,-n})
			auto lb = ver[p.second - n].upper_bound(p.first - n);
			auto ub = ver[p.second - n].lower_bound(p.first + n);
			if(lb != ver[p.second - n].end() and ub != ver[p.second - n].begin()){
				vector < int > willdel;
				for(auto it = lb;it != ub;++it){
					willdel.push_back(*it);
				}
				for(auto itr : willdel){
					bfs.push({-dist-1,{itr , p.second - n,}});
					ver[p.second - n].extract(itr);
					hor[itr].extract(p.second - n);
				}
			}
		}
		if(p.first != 0 and grid[p.first-1][p.second] == 0)bfs.push({-dist,{p.first-1,p.second}});
		if(p.second != 0 and grid[p.first][p.second-1] == 0)bfs.push({-dist,{p.first,p.second-1}});
		if(p.first != (r-1) and grid[p.first+1][p.second] == 0)bfs.push({-dist,{p.first+1,p.second}});
		if(p.second != (c-1) and grid[p.first][p.second+1] == 0)bfs.push({-dist,{p.first,p.second+1}});
		if((abs(g.first - p.first) <= n and abs(g.second - p.second) <= (n-1)) or (abs(g.first - p.first) <= (n-1) and abs(g.second - p.second) <= n)){
			bfs.push({-dist-1,g});
		}
	}
	cout << -1 << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

• 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: 0 / 8
• Subtask 8: 0 / 6