P2208 [USACO13OPEN]重力异常What's Up With Gravity

双端队列 + Hash判重广搜##

首先看到这么复杂的地图第一反应就是广搜了,,,
我觉得难点主要在

1. 每次扩展的时候花费不一定增大(也就是说如果使用普通队列是不满足单调性的, 答案可能会偏大)
2. 判重.

第二点如果想偷懒可以直接用set搞定, 如果追求速度的话可以手写Hash函数.
至于第一点嘛,,,我看有的人是用SPFA (@曹老师), 有的人是每次把当前相同花费的状态扩展完.
如果扩展完的话, 不仅代码会变长, 而且细节繁琐. 所以在这里我使用了双端队列(deque) 来处理.
对于当前状态扩展来的状态, 变化了重力的push_back, 其余的push_front, 这样就能解决队列单调性的问题了.

#include <set>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAXN = 5e2 + 10;

int N, M;
char mp[MAXN][MAXN];

struct state
{
    int x, y, val;
    bool g;//false->down, true-up;

    inline int Hash(){return ((x * 500 + y) << 1) | g;}
    inline int fall(){return x + (g ? -1 : 1);}
    inline bool out(){return !(1 <= x && x <= N && 1 <= y && y <= M);}

    void expand(vector<state> &cur){
        if(mp[fall()][y] != '#') {
            cur.push_back((state){fall(), y, val, g});
            return;
        }
        if(mp[x][y + 1] != '#') cur.push_back((state){x, y + 1, val, g});
        if(mp[x][y - 1] != '#') cur.push_back((state){x, y - 1, val, g});
        cur.push_back((state){x, y, val + 1, g ^ 1});
    }
};

bool vis[600000];
deque<state> q;
int bfs(){
    P s, t;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++){
            if(mp[i][j] == 'C') s = P(i, j);
            if(mp[i][j] == 'D') t = P(i, j);
        }
    q.push_back((state){s.first, s.second, 0, false});

    while(!q.empty()){
        state u = q.front(); q.pop_front();
        if(u.out()) continue;

        vector<state> nxt; u.expand(nxt);
        for(vector<state>::iterator it = nxt.begin(); it != nxt.end(); ++it){
            if(P(it->x, it->y) == t) return it->val;
            if(vis[it->Hash()]) continue;
            
            vis[it->Hash()] = true;
            if(it->val > u.val) q.push_back(*it);
            else q.push_front(*it);
        }
    }
    return -1;
}

int main()
{
    // freopen("p2208.in", "r", stdin);
    cin>>N>>M;
    for(int i = 1; i <= N; i++){
        scanf(" ");
        for(int j = 1; j <= M; j++)
            mp[i][j] = getchar();
    }
    cout<<bfs()<<endl;
    return 0;
}