背景 Background

一阵狂风吹过
只听“pong”的一声，飘飘乎居士降落了！！！
描述 Description

又是美妙的一天，这天飘飘乎居士要和MM约会，因此他打扮的格外帅气。但是，因为打扮的时间花了太久，离约会的时间已经所剩无几。
幸运的是，现在飘飘乎居士得到了一张nm的地图，图中左上角是飘飘乎居士的位置，右下角是约会的地点。‘.’代表马路，‘’代表房屋。飘飘乎居士只能沿着‘.’行走（也就是不能踏入‘’），而且行走的方向只能为上下左右的相邻格子。为了不让MM等待太久，飘飘乎居士在整个过程中可能会使用一次飘飘神功（也可能不使用，但最多使用一次），使用飘飘神功后，飘飘乎居士可以走进房屋一次（也就是在全程的行走中最多可以走一个‘’,注意，只有一个）；
现在飘飘乎居士想要知道最少需要走多少步，飘飘乎居士才能到达约会的地点。

输入格式 InputFormat

第一行，2个正整数 n和m，表示一个nm的矩阵
接下来n行，每行m个字符，字符一定为 ’.’ 或者是‘’ ，分别代表马路和房屋。
输入数据保证左上角和右下角都为‘.’
输出格式 OutputFormat

一行，如果可以到达，则输入需要行走的最少步数（飘飘神功也记为一步）
如果不可以到达，则输出‘no’
样例输入 SampleInput [复制数据]

样例输入1
3 3
.*.
…
…

样例输入2
3 3
.**

**.
样例输出 SampleOutput [复制数据]

样例输入1
4

样例输入2
no
数据范围和注释 Hint

0<N M <=1000
来源 Source

飘飘乎居士——violet hill

//————————————————————–

这道我的做法是分别由起点和终点开始，做两遍bfs，求出各自到其它点的最短距离，然后枚举使用飘飘神功的点，如果起点和终点都可以到达与该点相连并且相异的点就更新一下答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int MN = 1010;

struct pos{
    int x, y, deep;
};

queue<pos> q;

bool vis[MN][MN];
int a[MN][MN], b[MN][MN];
char c[MN][MN];
int n, m;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

bool check(pos t) {
    bool ret = (t.x >= 0 && t.y >= 0 && t.x < n && t.y < m);
    if (ret) {
        if (vis[t.x][t.y] || (c[t.x][t.y] == '*')) ret = false;
    }
    return ret;
}

void bfs(pos sr, int d[][MN]) {
    memset(vis, false, sizeof(vis));
    while (!q.empty()) q.pop();
    q.push(sr);
    vis[sr.x][sr.y] = true;
    d[sr.x][sr.y] = sr.deep;
    while (!q.empty()) {
        pos now, next;
        now = q.front();
        for (int i = 0; i < 4; i++) {
            next.x = now.x + dx[i];
            next.y = now.y + dy[i];
            if (check(next)) {
                next.deep = now.deep+1;
                d[next.x][next.y] = next.deep;
                q.push(next);
                vis[next.x][next.y] = true;
            }
        }
        q.pop();
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    memset(a, 63, sizeof(a));
    memset(b, 63, sizeof(b));
    int INF = a[0][0]; //!!!!!!
    pos sro, orz, l, r;
    sro.x = sro.y = sro.deep = 0;
    orz.x = n-1, orz.y = m-1, orz.deep = 0;
    bfs(sro, a);
    bfs(orz, b);
    int ans = INF;
    ans = min(ans, a[n-1][m-1]);
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (c[i][j] == '*') {
            for (int p = 0; p < 4; p++) {
                l.x = i+dx[p], l.y = j+dy[p];
                if (check(l))
                    for (int q = 0; q < 4; q++) if (p != q) {
                        r.x = i+dx[q], r.y = j+dy[q];
                        if (check(r)) {
                            ans = min(ans, a[l.x][l.y]+b[r.x][r.y]+2);
                        }
                    }
            }
        }
    }
    if (ans != INF)
        cout << ans << endl;
    else
        cout << "no" << endl;
    return 0;
}