Submission #1061631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061631		beaconmc	Maze (JOI23_ho_t3)	C++14	46 / 100	2095 ms	51680 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;

ll r,c,n;



vector<vector<ll>> grid;
vector<vector<ll>> visited;



bool iswithin(ll a, ll b, ll x, ll y){
	ll A = abs(x-a), B = abs(y-b);
	if ((A<=n && B < n) ||(A<n && B <= n)){
		return 1;
	}
	return 0;
}

vector<array<ll,2>> getvalid(ll a, ll b){
	vector<array<ll,2>> ans;

	FOR(i,-(n-1), n){
		ans.push_back({a-n, b+i});
		ans.push_back({a+n, b+i});
		ans.push_back({a+i, b-n});
		ans.push_back({a+i, b+n});
	}
	FOR(i,a-n,a+n+1){
		if (iswithin(a, b, i, c-1)) ans.push_back({i, c-1}); 
		if (iswithin(a, b, i, 0)) ans.push_back({i, 0}); 
	}
	FOR(i,b-n,b+n+1){
		if (iswithin(a,b,r-1,i)) ans.push_back({r-1, i});
		if (iswithin(a,b,0,i)) ans.push_back({0, i});
	}

	vector<array<ll,2>> realans;

	for (auto&i : ans){
		if (0<=i[0] && i[0]<r && 0<=i[1] && i[1]<c) realans.push_back(i);
	}

	return realans;
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> r >> c >> n;

	ll a,b;
	ll x,y;
	cin >> a >> b >> x >> y;
	a--;b--;x--;y--;
	
	FOR(i,0,r){

		vector<ll> temp;
		vector<ll> idk;

		string temp2;
		cin >> temp2;
		FOR(j,0,c){
			temp.push_back(temp2[j]);
			idk.push_back(100000000);

		}
		grid.push_back(temp);
		visited.push_back(idk);

	}




	ll ans = -1;

	deque<vector<ll>> sus;



	sus.push_back({a,b,0});
	visited[a][b] = 0;

	while (sus.size()){
		vector<ll> node = sus.front();
		sus.pop_front();


		if (visited[node[0]][node[1]] != node[2]) continue;


		if (node[0] == x && node[1] == y){
			ans = node[2];
			break;
		}
		if (iswithin(node[0],node[1],x,y)){
			if (visited[x][y]> node[2]+1){
				visited[x][y] = node[2]+1;
				sus.push_back({x,y,node[2]+1});
			}
			
		}


		vector<array<ll,2>> pos = {{node[0]-1,node[1]},{node[0]+1,node[1]},{node[0],node[1]-1},{node[0],node[1]+1}};

		vector<array<ll,2>> temp = getvalid(node[0], node[1]);

		for (auto&i : pos){
			if (0<=i[0] && i[0]<r && 0<=i[1] && i[1]<c){

				if (grid[i[0]][i[1]] == '.'){
					if (visited[i[0]][i[1]] > node[2]){
						visited[i[0]][i[1]] = node[2];
						sus.push_front({i[0], i[1], node[2]});
					}
				}
				else{

					if (visited[i[0]][i[1]] > node[2]+1 ){

						visited[i[0]][i[1]] = node[2]+1;
						sus.push_back({i[0], i[1], node[2]+1});
					}
				}
			}
		}

		for (auto&i : temp){
			if (visited[i[0]][i[1]] > node[2]+1){
				visited[i[0]][i[1]] = node[2]+1;
				sus.push_back({i[0], i[1], node[2]+1});
			}
		}

	}

	cout << ans << endl;








}

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