问题 F: 二师兄的纪录片

问题 F: 二师兄的纪录片
时间限制: 1 Sec 内存限制: 128 MB

题目描述
二师兄护送师傅取经成功之后，成了名人，他决定重新把取经的路再走一遍，并且拍摄一部纪录片宣传路上的风光。

从东土大唐到天竺的地图，是正方形的，城市坐落在 N 行 N 列的方形地图上。地图从位置（1，1）排列到位置（N，N）。地图上每一个格子是一座城市，上下左右直接相邻的城市之间可以一天到达。

有 P 座城市住着野蛮人（野蛮城市），他们只吃红烧肉。一天三顿红烧肉，连早餐都吃红烧肉。二师兄是出家人，决定不去这些城市。

另有 Q 座城市（友好城市）希望二师兄帮他们多宣传城市风光，所以给二师兄提供一个优惠条件：如果二师兄在这座城市（X）停留三天，就可以在第四天派专机把二师兄送到另外一座城市 Y。从城市 X 飞到城市 Y 可以瞬间完成，即：二师兄在到达X城市后，可以选择四天后到达Y城市。当然，二师兄也可以选择只在X城市停留一天，然后访问X城市直接相邻的城市。

已知长安城位于地图的（1，1）位置，目的地灵山位于地图的 （N，N）位置。每一个友好城市只能直飞到另外一个城市。

请求出二师兄从长安到达灵山最少需要多少天。
输入
输入数据第一行有三个整数，分别是 N，P，Q。
整数之间用空格分开。城市坐标系X轴向下，起点为1，Y 轴向右，起点为1。
数据接下来的 P 行，每行两个整数 a,b，代表某一个野蛮城市的坐标 (a,b)。
位置信息 (a,b) 表示在 X-Y 坐标系中的位置。
再接下来的 Q 行，每行四个整数，代表友好城市 X 的坐标和从X能直飞的城市 Y 的坐标。
输出
输出数据一行，表示二师兄从长安去往灵山最少需要多少天。
如果从长安到达不了灵山，则输出-1。
二师兄在长安出发那天记为第1天，到达灵山那天的日期就是输出数据。
样例输入 Copy
【样例1】
5 7 0
1 2
2 4
3 2
3 4
4 2
4 4
5 4
【样例2】
9 27 1
1 2
1 6
2 4
2 6
2 8
3 2
3 4
3 6
3 8
4 2
4 4
4 6
4 8
5 4
5 6
5 8
6 4
6 6
6 8
7 4
7 6
7 8
8 4
8 6
8 8
9 4
9 8
6 2 8 9
样例输出 Copy
【样例1】
11
【样例2】
12
提示
样例1解释样例数据后面的解释说明当中，“.”代表可以访问的普通城市，“#”代表野蛮城市。“1”代表X城市和能从“1”直飞的城市Y。

原地图：

样例1

到达目的地的走法：

样例2解释样例数据后面的解释说明当中，“.”代表可以访问的普通城市，“#”代表野蛮城市。“1”代表X城市和能从“1”直飞的城市Y。

原地图：

走法说明：走到 6 2 点的时候，穿越到 8 9 点。

题意： 从(1,1)走到(n,n)走法：可以往上，下，左，右走(代价是待天)，有$p$点不能走，有$q$个点可以传送(代价是待4天)问你走到(n,n)需要多长时间。
思路：
我的比较笨重，用了四个mp，不太提倡，但是也算一种思路，能ac都行。
具体说下四个mp的作用吧：

1. map mp;记录到达当前点pii最小代价
2. map mpp;记录传送点从第一个pii传送到第二个pii的
3. map mppp;记录是否能走
4. map mpppp;记录是否是传送点。

之后就是用其转化成dfs用上队列优化。
最后不要忘了他可能不会到达，不到达就是-1

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include 
#pragma GCC optimize(2)
#include 
#include 
#include 
#include
#include
#include
#include 
#include 
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=1e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
ll n,m,p,q;
string str;
ll a,b;
ll sum;
ll dp[150][150],vis[150][150];map<pii,ll> mp;
map<pii,ll> mppp;
map<pii,pii> mpp;
map<pii,ll> mpppp;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
void dfs(ll x,ll y){queue<pii>v;pii l;l={1,1};mp[l]=1;///步数v.push(l);while(!v.empty()){pii top=v.front();v.pop();ll num=mp[top];for(int i=0;i<4;i++){ll xx=top.first+dx[i],yy=top.second+dy[i];pii t;t={xx,yy};if(xx>=1&&yy>=1&&xx<=n&&yy<=n&&(mp[t]==0||mp[t]>num+1)&&mppp[t]==0){mp[t]=num+1;v.push(t);}}if(mpppp[top]){pii t=mpp[top];if((mp[t]>num+4||mp[t]==0)&&mppp[t]==0){mp[t]=num+4;v.push(t);}}}
}
int main() {cin>>n>>p>>q;for(int i=1;i<=p;i++){cin>>a>>b;pii t;t={a,b};mppp[t]=1;///标记不能走}for(int i=1;i<=q;i++){ll x,y,xx,yy;cin>>x>>y>>xx>>yy;pii l,r;l={x,y};mpppp[l]=1;///能传递r={xx,yy};mpp[l]=r;///传递给谁}dfs(1,1);pii ans;ans={n,n};if(mp[ans])cout<<mp[ans]<<endl;else cout<<-1<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！