https://loj.ac/problem/6121

BFS + 状压

写过就好想,注意细节debug

#include <bits/stdc++.h>
#define read read()
#define up(i,l,r) for(register int i = (l);i <= (r);i++)
#define down(i,l,r) for(register int i = (l);i >= (r);i--)
#define traversal_vedge(i) for(register int i = head[u]; i ;i = e[i].nxt)
#define ll long long
using namespace std;
int read
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-')f = -1; ch = getchar();}
    while(ch >=48 && ch <=57) {x = 10 * x + ch - 48;ch = getchar();}
    return x * f; 
}
void write(int x)
{
    if(x < 0) x = -x,putchar('-');
    if(x > 9) write(x/10);
    putchar(x%10 + 48);
}
//-----------------------------------------------------------------
const int N = 12;
int n,m,p,k,s;
int maps[N][N][N][N],cnt[N][N],type[N][N][N],vis[N][N][(1<<N)];
int dx[] = {0,0,0,-1,1},dy[] = {0,-1,1,0,0};

void readdata()
{
    n = read; m = read; p = read; k = read;
    int x1,x2,y1,y2,G;
    while(k--)
    {
        x1 = read; y1 = read; x2 = read; y2 = read; G = read;
        if(G) maps[x1][y1][x2][y2] = maps[x2][y2][x1][y1] = G;
        else maps[x1][y1][x2][y2] = maps[x2][y2][x1][y1] = -1;
    }
    s = read; int q;
    while(s--)
    {
        x1 = read; x2 = read; q = read;
        type[x1][x2][++cnt[x1][x2]] = q;
    }
}

struct node{
    int x,y,step,state;
};

int get_state(int x,int y)
{
    int ans = 0;
    up(i,1,cnt[x][y]) ans |= (1<<(type[x][y][i] - 1));
    return ans;
}

int bfs()
{
    queue <node> q;
    int s = get_state(1,1);
    q.push((node){1,1,0,s} );
    vis[1][1][s] = 1;
    while(!q.empty())
    {
        node u = q.front(); q.pop();
        int x = u.x,y = u.y;
        if(x == n && y == m) return u.step;
        up(i,1,4)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
            int obstacle = maps[x][y][nx][ny];
            if(obstacle == -1) continue;
            if( obstacle > 0 && (u.state & 1<<(obstacle - 1)) == 0 ) continue;//debug obstacle - 1 <- 1 - obstacle
            int ns = u.state|get_state(nx,ny);//degug u.state <- s;
            if(vis[nx][ny][ns]) continue;
            vis[nx][ny][ns] = 1;
            q.push( (node){nx,ny,u.step+1,ns} );
        }
    }
    return -1;
}

int main()
{
    freopen("input.txt","r",stdin);
    readdata();
    printf("%d\n",bfs());
    return 0;
}