BFS + 状压

写过就好想,注意细节debug

#include 
     
      #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 longusing 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<
      
        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;}