网站怎么做360免费优化/品牌网络推广外包

题意：给出起点终点，还有若干宝藏，问你能否走出迷宫，并尽可能带走价值最多的宝藏。

题解:最多有十个宝藏我们可以开一个三位数组vis[i][x][y]表示在x，y点已经拥有i状态的宝藏的。i有二进制压缩当前状态拥有的宝藏。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std;
struct node{int bit;int x,y,step;
};
const int maxn=55;  
bool vis[1100][maxn][maxn];
int n,m,l,ge;
char s[maxn][maxn];
int sx,sy,ex,ey;
int weigth[11];int Sum(int bit)
{int sum=0;for(int i=0;i<ge;i++){if((1<<i)&bit)sum+=weigth[i];}return sum;
}
int csa=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int bfs()
{memset(vis,0,sizeof(vis));  csa++;queue<node> q;node now;now.x=sx,now.y=sy;now.step=0;now.bit=0;q.push(now);vis[0][sx][sy]=1;int ans=0;while(!q.empty()){node u=q.front();q.pop();//printf("%d %d\n",u.x,u.y);for(int i=0;i<4;i++){int x=u.x,y=u.y,step=u.step,bit=u.bit;int x1=x+dx[i];int y1=y+dy[i];if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&s[x1][y1]!='*'){node v;v.x=x1;v.y=y1;v.step=step+1;if(s[x1][y1]>='A'&&s[x1][y1]<='Z')v.bit=(bit|(1<<(s[x1][y1]-'A')));else v.bit=bit;if(vis[v.bit][v.x][v.y]==1) continue;else vis[v.bit][v.x][v.y]=1;  if(s[x1][y1]=='<') ans=max(ans,Sum(v.bit));if(v.step==l) continue;q.push(v);}}}printf("Case %d:\n",csa);if(ans==0) printf("Impossible\n");else printf("The best score is %d.\n",ans);
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d%d",&m,&n,&l,&ge);for(int i=0;i<ge;i++) scanf("%d",&weigth[i]);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='<'){ex=i;ey=j;}if(s[i][j]=='@'){sx=i;sy=j;s[i][j]='.';}}}bfs();if(t!=0)printf("\n");}return 0;
}

另一种方法是bfs搜索任意两点最短距离，dfs搜索答案。