HDu-1044(bfs+圧力/dfs)

1235 ワード

标题:スタート地点のゴールを与えて、まだいくつかの宝があって、迷宮を出て、できるだけ価値の最も多い宝を持っていくことができるかどうかを聞いています.
标题:最大10個の宝がある私たちは3つの配列vis[i][x][y]を開いてxで、y点はすでにi状態の宝を持っていることを表すことができます.i現在の状態が持つ宝物をバイナリ圧縮する.
#include 
#include 
#include 
#include 
#include 
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 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
",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<

もう1つの方法はbfsが任意の2点の最短距離を検索し,dfsが答えを検索することである.