codevs1226 倒水问题

题目描述 Description

有两个无刻度标志的水壶，分别可装 x 升和 y 升（ x,y 为整数且均不大于 100 ）的水。设另有一水缸，可用来向水壶灌水或接从水壶中倒出的水，两水壶间，水也可以相互倾倒。已知 x 升壶为空壶， y 升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在x或y升的壶中量出 z （ z ≤ 100 ）升的水来。

输入描述 Input Description

一行，三个数据，分别表示 x,y 和 z;

输出描述 Output Description

一行，输出最小步数 ,如果无法达到目标，则输出"impossible"

样例输入 Sample Input

3 22 1

样例输出 Sample Output

思路：

普通广搜

代码：

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#define maxn 100000

using namespace std;

struct sta{

    int x;

    int y;

    int step;

    int frm;

};

int mx,my,z,j[][],solved = ;

sta temp;

void input(){

    cin>>mx>>my>>z;

    temp.x = temp.y = temp.step = ;

    temp.frm = -;

}

sta expand(sta a,int sign){

    if(sign == ) a.x = ;

    if(sign == ) a.y = ;

    if(sign == ) a.x = mx;

    if(sign == ) a.y = my;

    if(sign == ){

        int d;

        if(mx - a.x < a.y) d = mx - a.x;

        else d = a.y;

        a.y -= d;

        a.x += d;

    }

    if(sign == ){

        int d;

        if(my - a.y < a.x) d = my - a.y;

        else d = a.x;

        a.y += d;

        a.x -= d;

    }

    a.frm = sign;

    a.step++;

    if(j[a.x][a.y]) a.step = -;

    j[a.x][a.y] = ;

    return a;

}

void bfs(){

    sta q[maxn];

    int h = ,t = ;

    q[h] = temp;

    while(h != t){

        if(q[h%maxn].x == z || q[h%maxn].y == z) {

            cout<<q[h%maxn].step<<endl;

            solved = ;

            break;

        }

        for(int i = ;i <= ;i++){

           if(i ==  && (q[h%maxn].x ==  ||q[h%maxn].frm == )) continue;

           if(i ==  && (q[h%maxn].y ==  ||q[h%maxn].frm == )) continue;

           if(i ==  && (q[h%maxn].x == mx ||q[h%maxn].frm == )) continue;

           if(i ==  && (q[h%maxn].y == my ||q[h%maxn].frm == )) continue;

           if(i ==  && (q[h%maxn].y <=  || q[h%maxn].x >= mx || q[h%maxn].frm == )) continue;

           if(i ==  && (q[h%maxn].x <=  || q[h%maxn].y >= my || q[h%maxn].frm == )) continue;

           temp = expand(q[h%maxn],i);

           if(temp.step != -) {

               t++;

                   q[t%maxn] = temp;

           }

        }

        h++;

    }

}

int main(){

    input();

    if(z > mx || z > my || !mx || !my || (mx == my && mx != z)){

        cout<<"impossible"<<endl;

        return ;

    }

    bfs();

    if(!solved)    cout<<"impossible"<<endl;

    return ;

}

巴特西

codevs1226 倒水问题

最新文章

热门文章