本文主要是介绍HDU 1044 BFS+DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先BFS出每个点之间的最小距离
然后DFS最优值
#include "queue"
#include "iostream"
#include "algorithm"
using namespace std;int dir[4][2]={1,0,-1,0,0,1,0,-1};struct node
{int x,y,step;
};struct comp
{int x,y;
} mark[101];char str[101][101];
int w,h,l,m,maxx;
int hash[101][101];// 点是否走到过
int hash2[101]; // DFS标记
int map[101][101];
int value[101];int judge(int x,int y)
{if (x<0 || x>=h || y<0 || y>=w) return 0;if (hash[x][y]==1) return 0;if (str[x][y]=='*') return 0;return 1;
}void bfs(int x,int y,int w)
{queue<node>q;node cur,next;int tx,ty,i,temp;memset(hash,0,sizeof(hash));hash[x][y]=1;while (!q.empty())q.pop();cur.x=x;cur.y=y;cur.step=0;q.push(cur);while (!q.empty()){cur=q.front();q.pop();if (cur.step==l) return ;for (i=0;i<4;i++){tx=cur.x+dir[i][0];ty=cur.y+dir[i][1];if (judge(tx,ty)==0) continue;next.x=tx;next.y=ty;next.step=cur.step+1;if (str[tx][ty]=='<'){if (map[w][m+1]>next.step) map[w][m+1]=map[m+1][w]=next.step;}if (str[tx][ty]=='@'){if (map[w][0]>next.step) map[w][0]=map[0][w]=next.step;}if (str[tx][ty]>='A' && str[tx][ty]<='Z') {temp=str[tx][ty]-'A'+1;if (map[w][temp]>next.step) map[w][temp]=map[temp][w]=next.step;}hash[tx][ty]=1;q.push(next);}}return ;
}void dfs(int k,int w,int val) // k当前点，w当前代价，val当前价值
{int i,x;for (i=1;i<=m;i++)if (hash2[i]==0){if (w+map[k][i]+map[i][m+1]<=l) {x=val+value[i];if (x>maxx) maxx=x;hash2[i]=1;dfs(i,w+map[k][i],x);hash2[i]=0;}}return ;
}int main()
{int Case,ii,i,j;int first;scanf("%d",&Case);first=0;for (ii=1;ii<=Case;ii++){scanf("%d%d%d%d",&w,&h,&l,&m);for (i=0;i<=m+1;i++)for (j=0;j<=m+1;j++)if (i==j) map[i][j]=0;else map[i][j]=999999999;for (i=1;i<=m;i++)scanf("%d",&value[i]);getchar();for (i=0;i<h;i++)gets(str[i]);for (i=0;i<h;i++)for (j=0;str[i][j];j++){if (str[i][j]=='@')bfs(i,j,0);else if (str[i][j]=='<')bfs(i,j,m+1);else if (str[i][j]<='Z' && str[i][j]>='A')bfs(i,j,str[i][j]-'A'+1);}maxx=-1;memset(hash2,0,sizeof(hash2));hash2[0]=1;dfs(0,0,0);if (first==0) first=1; else printf("\n");printf("Case %d:\n",ii);if (maxx==-1)printf("Impossible\n");else printf("The best score is %d.\n",maxx);}return 0;
}这篇关于HDU 1044 BFS+DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
