Submission #933334

#	Time	Username	Problem	Language	Result	Execution time	Memory
933334		pcc	Maze (JOI23_ho_t3)	C++14	67 / 100	524 ms	261536 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll

/*
#define push_back push
#define pop_front pop
#define push_front push
#define front top


priority_queue<node,vector<node>,greater<node>> dq;
void add(int lvl ,int r,int c,int d){
	if(lvl>4||r<0||c<0||r>=R||c>=C)return;
	//cout<<lvl<<','<<r<<' '<<c<<' '<<d<<endl;
	if(dist[lvl][r][c] != -1&&dist[lvl][r][c]<=d)return;
	dist[lvl][r][c] = d;
	dq.push(node(lvl,r,c,d));
	return;
}
*/

struct node{
	int lvl,r,c,d;
	node(){lvl = r = c = d = 0;}
	node(int lv,int rr,int cc,int dd):lvl(lv),r(rr),c(cc),d(dd){}
	bool operator<(node b)const{
		return d<b.d;
	}
	bool operator>(node b)const{
		return d>b.d;
	}
};

int R,C,N;
vector<string> arr;
vector<vector<int>> dist[5];
pii s,e;

deque<node> dq;

pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};
pii dir2[] = {{1,1},{1,-1},{-1,-1},{-1,1}};

inline void add(int lvl,int r,int c,int d){
	if(lvl>4||r<0||c<0||r>=R||c>=C)return;
	//cout<<lvl<<','<<r<<' '<<c<<' '<<d<<endl;
	if(dist[lvl][r][c] != -1&&dist[lvl][r][c]<=d)return;
	dist[lvl][r][c] = d;
	if(dq.empty()||dq.back().d<=d)dq.push_back(node(lvl,r,c,d));
	else dq.push_front(node(lvl,r,c,d));
}

void add_center(int r,int c,int d){//extend radius of N square
	for(int i = 0;i<4;i++){
		int nr = r-dir2[i].fs*(N-1),nc = c-dir2[i].sc*(N-1);
		nr = min(nr,R-1),nr = max(nr,0ll),nc = min(nc,C-1),nc = max(nc,0ll);
		add(i,nr,nc,d);
	}
	return;
}

void BFS(pii s){
	add(4,s.fs,s.sc,0);
	dist[4][s.fs][s.sc] = 0;
	while(!dq.empty()){
		auto now = dq.front();
		dq.pop_front();
		if(dist[now.lvl][now.r][now.c] != now.d)continue;
		//cout<<now.lvl<<','<<now.r<<' '<<now.c<<':'<<now.d<<endl;
		if(now.lvl == 4){
			add_center(now.r,now.c,now.d+1);
			for(auto &d:dir){
				int nr = d.fs+now.r,nc = d.sc+now.c;
				//cout<<nr<<','<<nc<<endl;
				if(nr>=0&&nc>=0&&nr<R&&nc<C){
					add_center(nr,nc,now.d+1);
					add(4,nr,nc,now.d+(arr[nr][nc] == '#'));
				}
			}
		}
		else{
			add(4,now.r,now.c,now.d);
			int nr = now.r+dir2[now.lvl].fs,nc = now.c+dir2[now.lvl].sc;
			if(nr < 0||nc<0||nr>=R||nc>=C)continue;
			if(now.r%(N*2-1) != 0)add(now.lvl,nr,now.c,now.d);
			if(now.c%(N*2-1) != 0)add(now.lvl,now.r,nc,now.d);
		}
	}
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>R>>C>>N;
	arr = vector<string>(R);
	dist[0] = dist[1] = dist[2] = dist[3] = dist[4] = vector<vector<int>>(R,vector<int>(C,-1));
	cin>>s.fs>>s.sc>>e.fs>>e.sc;
	s.fs--,s.sc--,e.fs--,e.sc--;
	for(auto &i:arr)cin>>i;
	BFS(s);
	cout<<dist[4][e.fs][e.sc];
}

Compilation message (stderr)

Main.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~

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