FZU2188 – 过河I(BFS)

题目链接:FZU2188

【分析】用dis[i][j][k]表示右边有i只羊和j只狼最小需要几次,人在哪边(0左,1右)。首先动物数量只有200,状态不多,只有200*200*2,由于限制条件不较多,每个状态的决策原本是n^2的,可以剪掉很多所以时间够了,一开始想DP记忆化搜,突然发现不是DAG,DFS搜状态会回到原来出现过的,所以只能BFS搜,注意下细节耐心写没什么难度。具体看代码注释。

【AC CODE】796ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 200+10;
struct NODE{
	int rx,ry,f;
	NODE(int a, int b, int c){
		rx = a, ry = b, f = c;
	}
};
queue<NODE> q;
int x,y,n;
int dis[MAXN][MAXN][2];//dis[i][j][k]右边有i只羊和j只狼最小需要几次,人在哪边(0左,1右)
bool vis[MAXN][MAXN][2];

bool ok(int xx, int yy)
{
	if(xx) return xx >= yy;
	return true;
}
int bfs()
{
	while(!q.empty()) q.pop();
	clc(vis,0);
	dis[0][0][0] = 0;
	q.push(NODE(0,0,0));
	vis[0][0][0] = 1;
	while(!q.empty())
	{
		NODE now = q.front();q.pop();
		if(now.rx == x && now.ry == y) return dis[now.rx][now.ry][now.f];
		if(!now.f)//向右
		{
			int lx = x-now.rx, ly = y-now.ry;
			repe(i,1,lx)//羊
			{
				for(int j = 0; j <= ly && j <= i && i+j <= n; j++)//狼
				{
					if(ok(lx-i,ly-j) && ok(now.rx+i, now.ry+j) && !vis[now.rx+i][now.ry+j][!now.f])
					{
						q.push(NODE(now.rx+i,now.ry+j,!now.f));
						dis[now.rx+i][now.ry+j][!now.f] = dis[now.rx][now.ry][now.f]+1;
						vis[now.rx+i][now.ry+j][!now.f] = true;
					}
				}
			}
			//0羊
			for(int j = 1; j <= ly && j <= n; j++)
			{
				if(ok(lx,ly-j) && ok(now.rx,now.ry+j) && !vis[now.rx][now.ry+j][!now.f])
				{
					q.push(NODE(now.rx,now.ry+j,!now.f));
					dis[now.rx][now.ry+j][!now.f] = dis[now.rx][now.ry][now.f]+1;
					vis[now.rx][now.ry+j][!now.f] = true;
				}
			}
		}
		else//向左
		{
			int lx = x-now.rx, ly = y-now.ry;
			repe(i,1,now.rx)//羊
			{
				for(int j = 0; j <= now.ry && j <= i && i+j <= n; j++)//狼
				{
					if(ok(lx+i,ly+j) && ok(now.rx-i, now.ry-j) && !vis[now.rx-i][now.ry-j][!now.f])
					{
						q.push(NODE(now.rx-i, now.ry-j,!now.f));
						dis[now.rx-i][now.ry-j][!now.f] = dis[now.rx][now.ry][now.f]+1;
						vis[now.rx-i][now.ry-j][!now.f] = true;
					}
				}
			}
			//0羊
			for(int j = 1; j <= now.ry && j <= n; j++)
			{
				if(ok(lx,ly+j) && ok(now.rx,now.ry-j) && !vis[now.rx][now.ry-j][!now.f])
				{
					q.push(NODE(now.rx,now.ry-j,!now.f));
					dis[now.rx][now.ry-j][!now.f] = dis[now.rx][now.ry][now.f]+1;
					vis[now.rx][now.ry-j][!now.f] = true;
				}
			}
		}
	}
	return -1;
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	while(~scanf("%d %d %d%*c",&x, &y, &n))
	{
		if(x < y && x)
		{
			puts("-1");
			continue;
		}
		printf("%d\n", bfs());
	}
	return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

请输入正确的验证码