搜索

题意：

  • 给两个空瓶子以及它们的容量A，B
  • 三种操作
    • 倒满A或者B
    • 将A倒空或者将B倒空
    • 将A倒入B或者将B倒入A（倒满或者倒完）
  • 问任意一个瓶中的水达到C需要多少次操作

其实没有必要写题解…

唯一值得写的地方在于路径的输出：

  • 对于一些不需要输出具体操作的题，我们可以直接将上一步的操作序号直接存在数组中，比如x,y<1e9,那么可以使pre[xx][yy]=x*1e9+y,取出来的时候取余递归即可。
  • 对于需要输出操作顺序的题，我们可以直接开一个结构体，里面存着三个数组，分别记录前驱x，前驱y，以及操作i，这样可以避免在递归输出时额外花时间思考如何找出具体操作。
  • 实际上，pre数组可以当作vis使用，但是在空间足够的情况下，为了代码的易读性，还是使用额外的标记数组进行标记。
#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<string,pair<int,int> > pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn=1e2+10;
int A,B,goal;
int vis[maxn][maxn],last[maxn][maxn],lasta[maxn][maxn],lastb[maxn][maxn];
char p[][10] = {{},{"FILL(1)"},{"FILL(2)"},{"DROP(1)"},{"DROP(2)"},{"POUR(1,2)"},{"POUR(2,1)"}};

struct status{
	int a;
	int b;
	int step;
	status(int _a=0, int _b=0, int _step=0){
		a=_a;b=_b;step=_step;; 
	}
};

void print(int a, int b){
	if(last[a][b]!=0){
	    print(lasta[a][b],lastb[a][b]);
    	printf("%s\n",p[ last[a][b] ]);
  	}
}

void bfs(){
	queue<status>q;
	int flag = 0;
	q.push(status(0,0,0));
	vis[0][0] = 1;
	while(!q.empty()){
		status t = q.front(); q.pop();
		int a = t.a,b = t.b,step = t.step;
		if(a==goal||b==goal){
			cout<<step<<endl;
			flag = 1;
			print(a,b);
			break;
		}
		int t_a,t_b;
		if(a!=0){
			if(!vis[0][b]){//"DROP(1)
				q.push(status(0,b,step+1));
				lasta[0][b] = a;
				lastb[0][b] = b;
				last[0][b] = 3;
				vis[0][b] = 1;
			}
			if(a+b>=B){//POUR(1,2)
				t_b = B;
				t_a = a+b-B;
			}else{
				t_b = a+b;
				t_a = 0;
			}
			if(!vis[t_a][t_b]){
				q.push(status(t_a,t_b,step+1));
				lasta[t_a][t_b] = a;
				lastb[t_a][t_b] = b;
				last[t_a][t_b] = 5;
				vis[t_a][t_b] = 1;
			}
		}
		if(b!=0){
			if(!vis[a][0]){//"DROP(2)
				q.push(status(a,0,step+1));
				lasta[a][0] = a;
				lastb[a][0] = b;
				last[a][0] = 4;
				vis[a][0] = 1;
			}
			if(a+b>=A){//POUR(2,1)
				t_a = A;
				t_b = a+b-A;
			}else{
				t_a = a+b;
				t_b = 0;
			}
			if(!vis[t_a][t_b]){
				q.push(status(t_a,t_b,step+1));
				lasta[t_a][t_b] = a;
				lastb[t_a][t_b] = b;
				last[t_a][t_b] = 6;
				vis[t_a][t_b] = 1;
			}
		}
		if(a!=A){
			if(!vis[A][b]){
				q.push(status(A,b,step+1));
				lasta[A][b] = a;
				lastb[A][b] = b;
				last[A][b] = 1;//FILL(1)
				vis[A][b] = 1;
			}
		}
		if(b!=B){
			if(!vis[a][B]){
				q.push(status(a,B,step+1));
				lasta[a][B] = a;
				lastb[a][B] = b;
				last[a][B] = 2;//FILL(2)
				vis[a][B] = 1;
			}
		}
	}
	if(!flag){
		cout<<"impossible";
	}
}

一年以后重写代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
//#define CLR(a) memset(a,sizeof(a),0)

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int maxn=1e6+10;

int vis[200][200];
int pre[200][200];
int op[200][200];
int ans=0;
int out[maxn];
int cnt=0;

void bfs(int a,int b,int c){
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    queue<int>q;
    q.push(0);
    vis[0][0]=1;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        int x = t/1000;
        int y = t%1000;
        //cout<<x<<" "<<y<<endl;
        if(x==c||y==c){
            ans = x*1000+y;
            break;
        }
        int tx=x,ty=y;
        if(!vis[a][y]){
            pre[a][y]=x*1000+y;
            vis[a][y]=1;
            op[a][y]=1;
            q.push(a*1000+y);
        }
        if(!vis[x][b]){
            pre[x][b]=x*1000+y;
            vis[x][b]=1;
            op[x][b]=2;
            q.push(x*1000+b);
        }
        if(!vis[0][y]){
            pre[0][y]=x*1000+y;
            vis[0][y]=1;
            op[0][y]=3;
            q.push(0*1000+y);
        }
        if(!vis[x][0]){
            pre[x][0]=x*1000+y;
            vis[x][0]=1;
            op[x][0]=4;
            q.push(x*1000+0);
        }
        if(x>=b-y)tx = x-(b-y),ty=b;
        else tx = 0,ty = y+x;
        if(!vis[tx][ty]){
            pre[tx][ty]=x*1000+y;
            vis[tx][ty]=1;
            op[tx][ty]=5;
            q.push(tx*1000+ty);
        }
        if(y>a-x)ty = y-(a-x),tx=a;
        else ty = 0,tx = x+y;
        if(!vis[tx][ty]){
            pre[tx][ty]=x*1000+y;
            vis[tx][ty]=1;
            op[tx][ty]=6;
            q.push(tx*1000+ty);
        }
    }

}

void dfs(int num){
    if(num==0)return ;
    ++cnt;
    //if(cnt>10)return ;
    int x = num/1000;
    int y = num%1000;
    out[cnt]=op[x][y];
    dfs(pre[x][y]);
}

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    bfs(a,b,c);
    if(ans!=0){
        dfs(ans);
       // cout<<vis[0][5]<<endl;
        printf("%d\n",cnt);
        per(i,1,cnt){
            if(out[i]==1){
                puts("FILL(1)");
            }
            if(out[i]==2){
                puts("FILL(2)");
            }
            if(out[i]==3){
                puts("DROP(1)");
            }
            if(out[i]==4){
                puts("DROP(2)");
            }
            if(out[i]==5){
                puts("POUR(1,2)");
            }
            if(out[i]==6){
                puts("POUR(2,1)");
            }
        }
    }else{
        puts("impossible");
    }

    return 0;
}

发表评论

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