题解 P7904

· · 题解

BFS 练手题。

一开始就把所有起始点都放进队列里面，注意用优先队列，从步数最少的开始扩展。

转移状态时，我们记录当前点的上一步往哪个方向走，并记录坐标和步数。对于脚下的点按题意扩展方向，查重时要加一维表示方向。特别注意，脚下是 S 的时候可以向四方扩展，也不需要增加步数。

如果理解不了就看注释吧，也没啥好讲的。

代码：

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
inline int read() {
    int s = 0,f = 1;char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
    return s*f;
}
int n,m,A,B,C,D,tot;
char a[2010][2010];
bool vis[2010][2010][4];//查重带方向 
//0左1右2上3下 
//0: x,y-1
//1: x,y+1
//2: x-1,y
//3: x+1,y
struct node {
    int x,y,step,dir;
    bool operator < (const node &a) const {
        return step > a.step;//优先找步数最少的 
    }
};
pair<int,int> aa[4000010];
int bfs() {
    priority_queue<node> q;
    for (int i = 1;i <= tot;i ++ )//所有起始点 
    q.push({aa[i].first,aa[i].second,0,0});
    while (!q.empty()) {
        node t = q.top();q.pop();
        int x = t.x,y = t.y,d = t.dir,s = t.step;
        if (x < 1 || y < 1 || x > n || y > m) continue;
        if (a[x][y] == 'E') return s;//找到直接返回 
        if (vis[x][y][d]) continue;//查重 
        if (a[x][y] == '#') continue;
        if (a[x][y] == '|') {//按题意转移，画画图就理解了 
            if (d == 0 || d == 1) q.push({x-1,y,s+A,2}), q.push({x+1,y,s+A,3});
            if (d == 2) q.push({x-1,y,s+A,2});
            if (d == 3) q.push({x+1,y,s+A,3});
        }
        if (a[x][y] == '-') {
            if (d == 2 || d == 3) q.push({x,y-1,s+A,0}), q.push({x,y+1,s+A,1});
            if (d == 0) q.push({x,y-1,s+A,0});
            if (d == 1) q.push({x,y+1,s+A,1});
        }
        if (a[x][y] == '/') {
            if (d == 0) q.push({x+1,y,s+B,3});
            if (d == 1) q.push({x-1,y,s+B,2});
            if (d == 2) q.push({x,y+1,s+B,1});
            if (d == 3) q.push({x,y-1,s+B,0});
        }
        if (a[x][y] == '\\') {
            if (d == 0) q.push({x-1,y,s+B,2});
            if (d == 1) q.push({x+1,y,s+B,3});
            if (d == 2) q.push({x,y-1,s+B,0});
            if (d == 3) q.push({x,y+1,s+B,1});
        }
        if (a[x][y] == '.')
            q.push({x+1,y,s+C,3}),
            q.push({x-1,y,s+C,2}),
            q.push({x,y-1,s+C,0}),
            q.push({x,y+1,s+C,1});
        if (a[x][y] == '<') {
            if (d == 2 || d == 3) q.push({x,y-1,s+D,0});
            if (d == 0) q.push({x,y-2,s,0});
        }
        if (a[x][y] == '>') {
            if (d == 2 || d == 3) q.push({x,y+1,s+D,1});
            if (d == 1) q.push({x,y+2,s,1});
        }
        if (a[x][y] == '^') {
            if (d == 0 || d == 1) q.push({x-1,y,s+D,2});
            if (d == 2) q.push({x-2,y,s,2});
        }
        if (a[x][y] == 'v') {
            if (d == 0 || d == 1) q.push({x+1,y,s+D,3});
            if (d == 3) q.push({x+2,y,s,3});
        }
        if (a[x][y] == 'S')//起点的转移 
            q.push({x+1,y,s,3}),
            q.push({x-1,y,s,2}),
            q.push({x,y-1,s,0}),
            q.push({x,y+1,s,1});
        vis[x][y][d] = 1;
        if (a[x][y] == '.' || a[x][y] == 'S') vis[x][y][2] = vis[x][y][1] = vis[x][y][0] = vis[x][y][3] = 1;
        //优化，如果是这两个四面都标记，不加就T了。。 
        //其实本来是要在转移的时候就判重，只是懒得写 
    }
    return -1;//无解 
}
int main() {
    n = read(), m = read(), A = read(), B = read(), C = read(), D = read();
    for (int i = 1;i <= n;i ++ ) {
        scanf("%s",a[i]+1);
        for (int j = 1;j <= m;j ++ )
            if (a[i][j] == 'S')
                aa[++tot] = make_pair(i,j);
    }
    printf("%d",bfs());
    return 0;
}