优先队列做法

做法比较笨 为了过 没有简化代码

/**
 * 广搜变形
 * 双端队列BFS / 优先队列BFS
 * 添加一些剪枝:
 *   1. vis[][]数组剪枝
 *   2. 最优性剪枝 记录当前已经到达[x, y]的最小答案 若即将入队的tmp答案不可能小于ans 不如队
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;

int T, n, m;
bool Map[maxn][maxn];

struct Node{
    int x, y, step;
};
bool operator < (const Node &a, const Node &b){
    return a.step < b.step;
}
bool operator > (const Node &a, const Node &b){
    return a.step > b.step;
}
priority_queue<Node, vector<Node>, greater<Node> > pq;
int dx[4] = {-1, -1, 1, 1};
int dy[4] = {-1, 1, -1, 1};
int dn[4] = {0, 0, 1, 1};
int dm[4] = {0, 1, 0, 1};

bool valid(int xx, int yy){
    return xx >= 0 && xx <= n && yy >= 0 && yy <= m;
}

int main(){
    scanf("%d", &T);
    while(T--){
        while(pq.size()){
            pq.pop();
        }

        scanf("%d %d", &n, &m);
        getchar();
        char ch;
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= m; ++ j){
                ch = getchar();
                Map[i][j] = (ch == '/' ? 1 : 0);
            }
            getchar();
        }

        Node now;
        now.x = 0;
        now.y = 0;
        now.step = 0;
        bool vis[maxn][maxn] = {0};
        pq.push(now);

        bool flag = 0;
        int ans = 0x3f3f3f3f;
        while(pq.size()){
            now = pq.top();
            pq.pop();
            if(vis[now.x][now.y]) continue;
            vis[now.x][now.y] = 1;
            if(now.x == n && now.y == m){
                printf("%d\n", now.step);
                flag = 1;
                break;
            }
            for(int i = 0; i < 4; ++ i){
                int xx = now.x + dx[i];
                int yy = now.y + dy[i];
                if(valid(xx, yy) && !vis[xx][yy]){
                    Node tmp;
                    tmp.x = xx;
                    tmp.y = yy;
                    int nn = now.x + dn[i];
                    int mm = now.y + dm[i];
                    if(i == 0 || i == 3){
                        if(!Map[nn][mm]) tmp.step = now.step;
                        else tmp.step = now.step + 1;
                    }else{
                        if(Map[nn][mm]) tmp.step = now.step;
                        else tmp.step = now.step + 1;
                    }
                    if(tmp.x == n && tmp.y == m){
                        ans = min(ans, tmp.step);
                        pq.push(tmp);
                    }
                    else if(tmp.step < ans){
                        pq.push(tmp);
                    }
                }
            }
        }

        if(flag) continue;
        printf("NO SOLUTION\n");
    }
    return 0;
}