本文主要是介绍POJ 1324 状压搜索（4进制），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出图中蛇的范围和不可到达的地方，求蛇头到(1,1)点的最少代价
用4进制压缩存蛇身体相对蛇头的位置，BFS即可
特判蛇头在(1,1) 时的情况
注意位运算
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};struct node
{int x,y,step,status;
}cur,next;;
int n,m,l;
int map[21][21];
int hash[21][21][1<<14];
int judge(int x,int y,node a)
{int i;int ass[10];for (i=l-1;i>=1;i--){ass[i]=a.status&3;a.status>>=2;}for (i=1;i<l;i++){a.x+=dir[ass[i]][0];a.y+=dir[ass[i]][1];if (a.x==x && a.y==y) return 1;}return 0;
}
int find_dir(int x1,int y1,int x2,int y2)
{if (x1-1==x2) return 0;if (x1+1==x2) return 2;if (y1-1==y2) return 3;if (y1+1==y2) return 1;}
int bfs()
{queue<node>q;int lx,ly,f,k,x,y,i;scanf("%d%d",&cur.x,&cur.y);lx=cur.x;ly=cur.y;cur.step=cur.status=0;for (i=2;i<=l;i++){scanf("%d%d",&x,&y);if (x==lx-1) f=0;if (x==lx+1) f=2;if (y==ly-1) f=3;if (y==ly+1) f=1;lx=x; ly=y;cur.status=(cur.status<<2)+f;}hash[cur.x][cur.y][cur.status]=1;scanf("%d",&k);while(k--){scanf("%d%d",&x,&y);map[x][y]=1;}if(cur.x==1 && cur.y==1) return 0;q.push(cur);while(!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (next.x<1 || next.x>n || next.y<1 || next.y>m) continue;if (map[next.x][next.y]==1) continue;if (judge(next.x,next.y,cur)==1) continue;next.step=cur.step+1;next.status=(cur.status>>2);x=find_dir(next.x,next.y,cur.x,cur.y);next.status+=(x<<(2*l-4));if (hash[next.x][next.y][next.status]==1) continue;hash[next.x][next.y][next.status]=1;if (next.x==1 && next.y==1)return next.step;q.push(next);}}return -1;}
int main()
{int Case;Case=0;while (scanf("%d%d%d",&n,&m,&l)!=EOF){if (n+m+l==0) break;memset(hash,0,sizeof(hash));memset(map,0,sizeof(map));printf("Case %d: %d\n",++Case,bfs());}return 0;
}
这篇关于POJ 1324 状压搜索（4进制）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
