Submission #834980

#	Time	Username	Problem	Language	Result	Execution time	Memory
834980		sentheta	Maze (JOI23_ho_t3)	C++17	100 / 100	762 ms	205776 KiB

Main

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

#define V vector
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define Int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define ff first
#define ss second

#if VANWIJ
	#define DBG 1
#else
	#define DBG 0
#endif
#define cerr if(DBG) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;
#define _ << " " << 



const int INF = 1e9;

int r, c, n;

// start and goal
int sx, sy, gx, gy;

V<V<char>> a;

V<V<int>> nxth, nxtv;
int findH(int i,int j){
	if(nxth[i][j]==j) return j;
	return nxth[i][j] = findH(i, nxth[i][j]);
}
int findV(int i,int j){
	if(nxtv[i][j]==i) return i;
	return nxtv[i][j] = findV(nxtv[i][j], j);
}


V<V<int>> dist;
V<V<bool>> vis;

int minimum_stamps(int _r,int _c,int _n,int _sx,int _sy,int _gx,int _gy,V<V<char>>_a){
	r = _r; c = _c; n = _n;
	sx = _sx-1; sy = _sy-1; gx = _gx-1; gy = _gy-1;
	a.swap(_a);
	
	
	nxth = V<V<int>>(r+2, V<int>(c+2));
	nxtv = V<V<int>>(r+2, V<int>(c+2));
	rep(i,0,r+2) rep(j,0,c+2){
		nxth[i][j] = j;
		nxtv[i][j] = i;
	}
	
	
	dist = V<V<int>>(r, V<int>(c,INF));
	vis = V<V<bool>>(r, V<bool>(c));
	
	int ans = INF;
	
	V<pii> que[2];
	que[0].push_back({sx, sy});
	
	for(int d=0; ; d++){
		if(ans<=d) break;
		dbg(d);
		
		while(!que[d&1].empty()){
			auto[x,y] = que[d&1].back(); que[d&1].pop_back();
			if(vis[x][y]) continue;
			vis[x][y] = 1;
			
			cerr << x _ y << endl;
			
			if(x==gx && y==gy){
				ans = min(ans, d); break;
			}
			
			
			// go to neighbour
			for(int dir : {1,3,5,7}){
				int i = x+dir%3-1, j = y+dir/3-1;
				if(0<=i && i<r && 0<=j && j<c && a[i][j]=='.' && d<dist[i][j]){
					que[d&1].push_back({i, j});
				}
			}
			
			// goal is in stamp proximity
			bool nearGoal = 0;
			nearGoal |= abs(gx-x)<=n && abs(gy-y)<n;
			nearGoal |= abs(gx-x)<n && abs(gy-y)<=n;
			if(nearGoal){
				dbg(x); dbg(y);
				ans = min(ans, d+1);
			}
			
			// go to stamp
			// for(int i=x-n; i<=x+n; i++) if(0<=i && i<r)
			// for(int j=y-n; j<=y+n; j++) if(0<=j && j<c)
			// if(!(abs(i-x)==n && abs(j-y)==n))
			// {
			// 	que[~d&1].push({i,j});
			// }
			
			// (x+n, ..)
			{
				int i=min(x+n,r-1), j=max(y-(n-1),0);
				j = findH(i,j);
				while(j <= min(y+(n-1),c-1)){
					if(d+1 < dist[i][j]){
						que[~d&1].push_back({i, j}); dist[i][j] = d+1;
					}
					nxth[i][j] = j+1;
					j = findH(i,j);
				}
			}
			// (x-n, ..)
			{
				int i=max(x-n,0), j=max(y-(n-1),0);
				j = findH(i,j);
				while(j <= min(y+(n-1),c-1)){
					if(d+1 < dist[i][j]){
						que[~d&1].push_back({i, j}); dist[i][j] = d+1;
					}
					nxth[i][j] = j+1;
					j = findH(i,j);
				}
			}
			// (.., y+n)
			{
				int i=max(x-(n-1),0), j=min(y+n,c-1);
				i = findV(i,j);
				while(i <= min(x+(n-1),r-1)){
					if(d+1 < dist[i][j]){
						que[~d&1].push_back({i, j}); dist[i][j] = d+1;
					}
					nxtv[i][j] = i+1;
					i = findV(i,j);
				}
			}
			// (.., y-n)
			{
				int i=max(x-(n-1),0), j=max(y-n,0);
				i = findV(i,j);
				while(i <= min(x+(n-1),r-1)){
					if(d+1 < dist[i][j]){
						que[~d&1].push_back({i, j}); dist[i][j] = d+1;
					}
					nxtv[i][j] = i+1;
					i = findV(i,j);
				}
			}
		
		}
		
	}
	
	
	return ans;
	
}



int main() {
  int R, C, N, Sr, Sc, Gr, Gc;
  assert(3 == scanf("%d %d %d", &R, &C, &N));
  assert(2 == scanf("%d %d", &Sr, &Sc));
  assert(2 == scanf("%d %d", &Gr, &Gc));
  std::vector<std::vector<char>> A(R, std::vector<char>(C));
  for (int i = 0; i < R; ++i) {
    getchar();  // Read endline
    for (int j = 0; j < C; ++j) {
      scanf("%c", &A[i][j]);
    }
  }

  printf("%d\n", minimum_stamps(R, C, N, Sr, Sc, Gr, Gc, A));
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:179:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |       scanf("%c", &A[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~

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