Zerojudge j249 市區導航路線規畫

tags: 競程題解,競程

Timestamp ： 2023/02/28 20:43

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << "\n";
#define DB(x) cerr << #x << " " << x << "\n"
#define all(v) v.begin(), v.end()
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#endif
const int INF = 0x3f3f3f3f3f3f3f3f;
const int P = 1e9+7;
using namespace std;
/******************************************************************************/

int dis[4][510][510]={};
bool spe[510][510]={};
int cx[]={0,-1,0,1},cy[]={-1,0,1,0};
signed main(){
	AC
	queue<pii> qb;
	int m,n,p,q,a,b;
	cin>>m>>n>>p>>q>>a>>b;
	pii end = {a,b};
	memset(dis,0x3f,sizeof(dis));
	while(p--){
		cin>>a>>b;
		dis[0][a][b]=dis[1][a][b]=dis[2][a][b]=dis[3][a][b]=-1e9;
	}
	while(q--){
		cin>>a>>b;
		spe[a][b]=1;
	}
	a=b=0;
	dis[0][a][b]=dis[1][a][b]=dis[2][a][b]=dis[3][a][b]=0;
	qb.push({0,0});
	while(qb.size()){
		auto now = qb.front();
		qb.pop();
		int x = now.F,y = now.S;
		if(spe[x][y]){
			for(int c=0;c<4;c++){
				int nx = x+cx[c],ny = y+cy[c];
				if(nx<0||ny<0||nx>=m||ny>=n)continue;
				int tranmin=1e9;
				for(int cc=0;cc<4;cc++){
					if(cc==(c+1)%4)continue;
					if((c+2)%4==cc)continue;
					tranmin = min(dis[cc][x][y],tranmin);
				}
				
				if(dis[c][nx][ny]>tranmin+1){
					dis[c][nx][ny]=tranmin+1;
					qb.push({nx,ny});
				}
			}
		}
		else{
			
			for(int c=0;c<4;c++){
				int tranmin=1e9;
				for(int cc=0;cc<4;cc++){
					if((c+2)%4==cc)continue;
					tranmin = min(dis[cc][x][y],tranmin);
				}
				int nx = x+cx[c],ny = y+cy[c];
				if(nx<0||ny<0||nx>=m||ny>=n)continue;
				if(dis[c][nx][ny]>tranmin+1){
					dis[c][nx][ny]=tranmin+1;
					qb.push({nx,ny});
				}
			}
		}
	}

	int tranmin=1e9;
	for(int cc=0;cc<4;cc++){
		tranmin = min(dis[cc][end.F][end.S],tranmin);
	}
	cout<<tranmin<<"\n";
}