首页 > 代码库 > HDU 5025 状态压缩蛇+bfs+dp
HDU 5025 状态压缩蛇+bfs+dp
题目大意:
孙悟空要找到一条花费时间最短的路径，路上为S的代表有蛇，经过需多花一分钟，其他情况下都是走过花费一分钟，但数字必须依次得到，最后到了唐僧处，可以经过也可以救出，救出前提是得到所有种类的钥匙
这道题，我们不断找到到达每一个点的不同状态下的最小花费时间，用dp[N][N][11][status]来存，status代表所有蛇的状态，因为蛇只有5条，所以status<32，不会爆掉。
类似spfa中不断对某个状态进行弛缓操作，如果成功就更新数据后入队，否则不再入队。
这题之所以不能dfs来做，是因为dfs不断从一个点出发搜索一条连续的值，这里因为可以重复经过，也无法设置visit量，而且对于某一点来说到起点的曼哈顿距离都是一样的，由前一个状态确认下一个状态的最好方法还是bfs，bfs过程需要注意什么时候入队，出队，数据的更新。dfs重复操作太多，也会超时。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 #define N 102 9 int pos[N][N]; 10 11 struct Node{ 12 int x,y,key,status; 13 }; 14 15 char mat[N][N]; 16 int dp[N][N][11][1<<5],n,m; 17 int a,b,c,d,s[N][N]; 18 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 19 queue<Node> q; 20 21 void ok(Node p1,Node p2,int x) 22 { 23 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+x) 24 { 25 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+x; 26 //printf("%d %d %d\n",p2.x,p2.y,dp[p2.x][p2.y][p2.key][p2.status]); 27 q.push(p2); 28 } 29 } 30 31 void bfs(int x,int y) 32 { 33 while(!q.empty()) 34 q.pop(); 35 36 Node t; 37 t.x=x,t.y=y,t.key=0,t.status=0; 38 q.push(t); 39 while(!q.empty()){ 40 41 Node p1 = q.front(); 42 q.pop(); 43 44 for(int i=0;i<4;i++){ 45 Node p2; 46 p2.x = p1.x+dir[i][0]; 47 p2.y = p1.y+dir[i][1]; 48 if(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<n&&mat[p2.x][p2.y]!=‘#‘){ 49 if(mat[p2.x][p2.y]==‘.‘){ 50 p2.key = p1.key; 51 p2.status = p1.status; 52 //kcout<<"in.."<<endl; 53 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+1) 54 { 55 //cout<<"in.."<<endl; 56 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+1; 57 q.push(p2); 58 } 59 } 60 61 else if(mat[p2.x][p2.y]==‘S‘){ 62 int ins = pos[p2.x][p2.y]; 63 //cout<<"inS"<<endl; 64 if(p1.status & 1<<(ins-1)){ 65 p2.key = p1.key; 66 p2.status = p1.status; 67 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+1) 68 { 69 // cout<<"inS"<<endl; 70 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+1; 71 q.push(p2); 72 } 73 } 74 else{ 75 p2.key = p1.key; 76 p2.status = p1.status|1<<(ins-1); 77 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+2) 78 { 79 // cout<<"inS"<<endl; 80 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+2; 81 q.push(p2); 82 } 83 } 84 85 } 86 87 else if(mat[p2.x][p2.y]==‘T‘){ 88 p2.key = p1.key; 89 p2.status = p1.status; 90 91 if(p1.key == m){ 92 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+1) 93 { 94 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+1; 95 } 96 } 97 else{ 98 if(dp[p2.x][p2.y][p2.key][p2.status]>dp[p1.x][p1.y][p1.key][p1.status]+1) 99 {100 dp[p2.x][p2.y][p2.key][p2.status]=dp[p1.x][p1.y][p1.key][p1.status]+1;101 }102 q.push(p2);103 }104 }105 106 else{107 int tmp = mat[p2.x][p2.y] - ‘0‘;108 if(tmp == p1.key+1) {109 p2.key = p1.key+1;110 p2.status = p1.status;111 ok(p1,p2,1);112 }113 else{114 p2.key = p1.key;115 p2.status = p1.status;116 ok(p1,p2,1);117 }118 }119 }120 }121 }122 }123 124 int main()125 {126 while(~scanf("%d%d",&n,&m)){127 if(n==0&&m==0)128 break;129 130 int tmp = 0;131 memset(dp,0x3f,sizeof(dp));132 133 for(int i=0;i<n;i++){134 for(int j=0;j<n;j++){135 cin>>mat[i][j];136 if(mat[i][j] == ‘K‘)137 a=i,b=j;138 else if(mat[i][j] == ‘T‘)139 c=i,d=j;140 141 else if(mat[i][j] == ‘S‘)142 pos[i][j]=++tmp;143 }144 }145 146 //确定孙悟空出发点后可以把当前点想象成和‘.‘一样的功能147 mat[a][b] = ‘.‘;148 dp[a][b][0][0] = 0;149 bfs(a,b);150 151 int minn = 0x3f3f3f3f;152 153 for(int i = 0;i<32;i++){154 //printf("%d\n",dp[c][d][m][i]);155 if(dp[c][d][m][i]<minn)156 minn = dp[c][d][m][i];157 }158 159 if(minn == 0x3f3f3f3f)160 printf("impossible\n");161 else162 printf("%d\n",minn);163 }164 return 0;165 }
HDU 5025 状态压缩蛇+bfs+dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。