Submission #878466

#	Time	Username	Problem	Language	Result	Execution time	Memory
878466		phoenix0423	Maze (JOI23_ho_t3)	C++17	27 / 100	2072 ms	15184 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int INF = 1e9;

struct pt{
	int x, y;
	pt(){}
	pt(int _x, int _y) : x(_x), y(_y){}
	bool operator < (const pt& other) const{
		return x < other.x;
	}
};
istream &operator>> (istream &s, pt &p){
	s >> p.x >> p.y;
	return s;
}
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main(void){
	// fastio;
	int r, c, n;
	cin>>r>>c>>n;
	pt st, ed;
	cin>>st>>ed;
	st.x--, st.y--, ed.x--, ed.y--;
	vector<string> s(r);
	REP(i, r) cin>>s[i];
	vector<vector<int>> dist(r, vector<int>(c, INF));
	dist[st.x][st.y] = 0;
	typedef pair<int, pt> pipt;
	priority_queue<pipt, vector<pipt>, greater<pipt>> q;
	q.push({0, st});
	auto inbound = [&](int x, int y) -> bool{
		return x >= 0 && y >= 0 && x < r && y < c;
	};
	while(!q.empty()){
		auto [dis, pos] = q.top(); q.pop();
		auto [x, y] = pos;
		if(dist[x][y] != dis) continue;
		for(int d = 0; d < 4; d++){
			int xx = x + dx[d], yy = y + dy[d];
			if(!inbound(xx, yy) || s[xx][yy] == '#') continue;
			if(dist[xx][yy] > dist[x][y]){
				dist[xx][yy] = dist[x][y];
				q.push({dist[x][y], pt(xx, yy)});
			}
		}
		for(int xx = x - n; xx <= x + n; xx++){
			for(int yy = y - n; yy <= y + n; yy++){
				if(!inbound(xx, yy)) continue;
				int tk = (xx == x - n) + (xx == x + n) + (yy == y - n) + (yy == y + n);
				if(tk == 2) continue;
				if(dist[xx][yy] > dist[x][y] + 1){
					dist[xx][yy] = dist[x][y] + 1;
					q.push({dist[xx][yy], pt(xx, yy)});
				}
			}
		}
	}
	cout<<dist[ed.x][ed.y]<<"\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 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