题目链接: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; }