Submission #741941

#	Time	Username	Problem	Language	Result	Execution time	Memory
741941		jamezzz	Maze (JOI23_ho_t3)	C++17	100 / 100	1420 ms	276360 KiB

Main

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define INF 1023456789
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;

#define maxn 120005

int r,c,n,sr,sc,gr,gc;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
vector<vector<int>> grid,dist;
vector<vector<ii>> dist2;

inline bool bad(int x,int y){
	return x<0||y<0||x>=r||y>=c;
}

int main(){
	sf("%d%d%d%d%d%d%d",&r,&c,&n,&sr,&sc,&gr,&gc);
	--sr;--sc;--gr;--gc;
	grid.resize(r);
	dist.resize(r);
	dist2.resize(r);
	for(int i=0;i<r;++i){
		grid[i].resize(c);
		dist[i].resize(c,INF);
		dist2[i].resize(c,{INF,INF});
		for(int j=0;j<c;++j){
			char ch;sf(" %c",&ch);
			grid[i][j]=(ch=='#');
		}
	}
	queue<ii> bfs;
	dist[sr][sc]=0;
	bfs.push({sr,sc});
	int cur=0;
	while(!bfs.empty()){
		vector<ii> good;
		//pf("cur: %d\n",cur);
		while(!bfs.empty()){
			auto[x,y]=bfs.front();bfs.pop();
			dist[x][y]=cur;
			good.pb({x,y});
			//pf("bfs1 %d %d\n",x,y);
			for(int i=0;i<4;++i){
				int nx=x+dx[i],ny=y+dy[i];
				if(!bad(nx,ny)&&grid[nx][ny]==0&&dist[x][y]<dist[nx][ny]){
					dist[nx][ny]=dist[x][y];
					bfs.push({nx,ny});
				}
			}
		}
		queue<ii> bfs2;
		for(auto[x,y]:good){
			for(int i=0;i<4;++i){
				int nx=x+dx[i],ny=y+dy[i];
				if(!bad(nx,ny)&&dist[nx][ny]==INF&&dist2[nx][ny].fi==INF){
					dist2[nx][ny]={abs(dx[i]),abs(dy[i])};
					bfs2.push({nx,ny});
				}
			}
		}
		while(!bfs2.empty()){
			auto[x,y]=bfs2.front();bfs2.pop();
			//pf("bfs2 %d %d\n",x,y);
			bfs.push({x,y});
			for(int i=0;i<4;++i){
				int nx=x+dx[i],ny=y+dy[i];
				if(!bad(nx,ny)&&dist[nx][ny]==INF&&dist2[nx][ny].fi==INF){
					ii tmp={dist2[x][y].fi+abs(dx[i]),dist2[x][y].se+abs(dy[i])};
					if(max(tmp.fi,tmp.se)<=n&&min(tmp.fi,tmp.se)<n&&dist2[nx][ny]>tmp){
						dist2[nx][ny]=tmp;
						bfs2.push({nx,ny});
					}
				}
			}
		}
		/*
		for(int i=0;i<r;++i){
			for(int j=0;j<c;++j){
				if(dist[i][j]==INF){
					pf("%c",grid[i][j]?'#':'.');
				}
				else pf("%d",dist[i][j]);
			}
			pf("\n");
		}
		*/
		++cur;
	}
	pf("%d\n",dist[gr][gc]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  sf("%d%d%d%d%d%d%d",&r,&c,&n,&sr,&sc,&gr,&gc);
      |    ^
Main.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    char ch;sf(" %c",&ch);
      |              ^

• 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