Submission #1061526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061526		beaconmc	Maze (JOI23_ho_t3)	C++14	8 / 100	319 ms	33252 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<bool>> visited;
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});
	}

	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<bool> idk;
		string temp2;
		cin >> temp2;
		FOR(j,0,c){
			temp.push_back(temp2[j]);
			idk.push_back(0);
		}
		grid.push_back(temp);
		visited.push_back(idk);
	}


	ll ans = -1;

	deque<vector<ll>> sus;

	sus.push_back({a,b,0});
	visited[a][b] = 1;
	while (sus.size()){
		vector<ll> node = sus.front();
		sus.pop_front();


		if (node[0] == x && node[1] == y){
			ans = node[2];
			break;
		}


		vector<vector<ll>> pos = {{node[0]-1,node[1]},{node[0]+1,node[1]},{node[0],node[1]-1},{node[0],node[1]+1}};
		for (auto&i : pos){
			if (0<=i[0] && i[0]<r && 0<=i[1] && i[1]<c && !visited[i[0]][i[1]]){
				visited[i[0]][i[1]] = 1;

				if (grid[i[0]][i[1]] == '.') sus.push_front({i[0], i[1], node[2]});
				else sus.push_back({i[0], i[1], node[2]+1});
			}
		}
	}
	cout << ans << endl;








}

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