题目名称：二师兄的纪录片 提交通过率：22%

测评方式 标准输入输出

时间限制 3000ms

内存限制 256MB

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

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

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

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

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

请求出二师兄从长安到达灵山最少需要多少天。

题目背景 对于 25% 数据，Q=0，2≤N ≤10。 对于 50% 数据，Q=0， 2≤N ≤1000。 对于 75% 数据， 2≤N ≤1000 。 对于 100% 数据， 0≤Q≤100 ， 2≤N ≤2000 。 空间不超过 256M 字节； 时间不超过 1.5 秒。 输入描述 输入数据第一行有两个整数，分别是 N，Q。整数之间用空格分开。 城市坐标系 X 轴向下，起点为 1，Y 轴向右，起点为 1。 数据接下来的 N 行，每行 N 个字符表示地图。地图中点('.') 表示一般城市，井号('#')表示野蛮城市。 再接下来的 Q 行，每行四个整数，代表友好城市 X 的坐标和从 X 能直飞的城市 Y 的坐标。

输出描述

输出数据一行，表示二师兄从长安去往灵山最少需要多少天。 如果从长安到达不了灵山，则输出 -1。 二师兄在长安出发那天记为第 1 天，到达灵山那天的日期就是输出数据。

样例1

输入复制

5 0

.#...

...#.

.#.#.

.#.#.

...#.

输出

11

代码：

---

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int n,q;
char a[2005][2005];
int dist[2005][2005];
map <pair<int,int>,pair<int,int> > mp;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
struct Node{
    int x,y,w;
    bool operator < (const Node &b) const {
        return w>b.w;
    }
};
void dij(){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            dist[i][j] = INT_MAX;
        }
    }
    dist[1][1] = 1;
    priority_queue <Node> q;
    q.push({1,1,1});
    int x,y;
    bool st[2005][2005] = {0};
    while(q.size()){
        x = q.top().x;
        y = q.top().y;
        q.pop();
        for(int k = 0;k<4;k++){
            int nx = x+dx[k],ny = y+dy[k];
            if(nx<1 || ny<1 || nx>n || ny>n) continue;
            if(a[nx][ny] == '#') continue;
            if(dist[x][y]+1 < dist[nx][ny]){ 
                dist[nx][ny] = dist[x][y]+1;
                q.push({nx,ny,dist[nx][ny]});
            }
        }
    }
    if(mp.find(make_pair(x,y))!=mp.end()){
        auto tmp = mp[make_pair(x,y)];
        int nx = tmp.first,ny = tmp.second;
        if(dist[x][y] +4<dist[nx][ny]){
            dist[nx][ny] = dist[x][y]+4;
            q.push({nx,ny,dist[nx][ny]});
        }
    }
    if(dist[n][n] == INT_MAX) cout << -1;
    else cout << dist[n][n];
}
int main(){
    cin >> n>> q;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin >> a[i][j];
        }
    }
    while(q--){
        int x_1,y_1,x_2,y_2;
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        mp[make_pair(x_1,y_1)] = make_pair(x_2,y_2);
        //mp[make_pair(x_2,y_2)] = make_pair(x_1,y_1);
    }
    dij();
    return 0;
}