HihoCoder 1328 BFS 搜索

题目链接

---

BFS模板
状态标记为四元组(x,y,key,t)，二进制表示得到的钥匙

注意：
== 的运算优先级比 & 高

一个位置可以有多把钥匙，而且钥匙可以在对应的门里面。
所以要先判断门可不可以进，在判断可不可以得到新钥匙。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <ctype.h>
using namespace std;
const int N = 1e6 + 5;
int n,m,k,a,b,c,d;
struct Node
{
    int x,y;
    int key;
    int t;
    Node(){}
    Node(int a,int b,int c,int d): x(a), y(b), key(c), t(d) {}
};
int kx[6],ky[6];
bool vis[N];
int dirx[] = {0,1,0,-1};
int diry[] = {1,0,-1,0};
void init()
{
    memset(vis, 0, sizeof(vis));
}
char mp[105][105];
int getStatus(int x, int y, int key)
{
    return x*10000+y*100+key;
}
int getkey(int x, int y)
{
    int key = 0;
    for(int i = 0; i < k; i++)
    {
        if(x == kx[i] && y == ky[i])
        {
            key |= 1 << i;
        }
    }
    return key;
}

int bfs()
{
    queue<Node> Q;
    int st = getStatus(a,b,0);
    vis[st] = 1;
    Q.push(Node(a,b,0,0));

    while(!Q.empty())
    {
        Node node = Q.front(); Q.pop();
        int x = node.x, y = node.y, key = node.key, t = node.t;
        if(x == c && y == d) return t;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dirx[i], ny = y + diry[i], nt = t + 1, nkey = key;
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(mp[nx][ny] == '#') continue;
            if(isupper(mp[nx][ny]))
            {
                int p = mp[nx][ny] - 'A';
                if((nkey & (1<<p)) == 0) continue;
            }
            int p;
            if( (p=getkey(nx,ny)) > 0)
            {
                nkey |= p;
            }
            int st = getStatus(nx,ny,nkey);
            if(vis[st]) continue;
            vis[st] = 1;
            Q.push(Node(nx,ny,nkey,nt));
        }
    }
    return -1;
}


int main()
{
    scanf("%d%d%d%d%d%d%d", &n,&m,&k,&a,&b,&c,&d);
    getchar();
    for(int i = 0; i < n; i++)
        gets(mp[i]);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%d", &kx[i], &ky[i]);
    }
    init();
    int t = bfs();
    printf("%d
", t);
    return 0;
}