首页 > 代码库 > HDU 4771 BFS&状压 水
HDU 4771 BFS&状压 水
n*m矩阵,起点@,从矩阵中拿k个物品的最小代价
水BFS
#include "stdio.h" #include "string.h" #include "queue" using namespace std; int b[]={1,2,4,8,16}; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; struct node { int x,y,step,status; }; int n,m,aim,s_x,s_y; char str[110][110]; int hash[110][110][20]; int bfs() { queue<node>q; node cur,next; int i; cur.x=s_x; cur.y=s_y; cur.step=0; cur.status=0; memset(hash,0,sizeof(hash)); hash[s_x][s_y][0]=1; 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<0 || next.y<0 || next.x>=n || next.y>=m) continue; if (str[next.x][next.y]=='#') continue; next.status=cur.status; if (str[next.x][next.y]<=8) next.status|=str[next.x][next.y]; if (hash[next.x][next.y][next.status]==1) continue; hash[next.x][next.y][next.status]=1; next.step=cur.step+1; if (next.status==aim) return next.step; q.push(next); } } return -1; } int main() { int i,j,k; while (scanf("%d%d",&n,&m)!=EOF) { if (n+m==0) break; for (i=0;i<n;i++) scanf("%s",str[i]); for (i=0;i<n;i++) for (j=0;j<m;j++) if(str[i][j]=='@') { s_x=i; s_y=j; } scanf("%d",&k); aim=b[k]-1; while(k--) { scanf("%d%d",&i,&j); i--; j--; str[i][j]=b[k]; } printf("%d\n",bfs()); } return 0; }
HDU 4771 BFS&状压 水
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。