程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ21 三個水杯 (經典問題 bfs)

NYOJ21 三個水杯 (經典問題 bfs)

編輯：C++入門知識

NYOJ21 三個水杯 (經典問題 bfs)

給出三個水杯，大小不一，並且只有最大的水杯的水是裝滿的，其余兩個為空杯子。三個水杯之間相互倒水，並且水杯沒有標識，只能根據給出的水杯體積來計算。現在要求你寫出一個程序，使其輸出使初始狀態到達目標狀態的最少次數。

輸入第一行一個整數N(0 接下來每組測試數據有兩行，第一行給出三個整數V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三個水杯的體積。
第二行給出三個整數E1 E2 E3 （體積小於等於相應水杯體積）表示我們需要的最終狀態輸出每行輸出相應測試數據最少的倒水次數。如果達不到目標狀態輸出-1樣例輸入

樣例輸出

3
-1

題目分析：

經典題目，bfs搜索，不用回溯，直接暴力即可。

AC代碼：

 
/**
 *bfs,隱式圖的搜索
 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int vis[101][101][101];//記錄是否被訪問
struct StateNode{
    int cur[3];//記錄當前狀態
    int v[3];//記錄狀態
    int step;//步數
};
queue q;
int Sucess(StateNode a,StateNode b){//比較是否相等
    return (a.cur[0] == b.cur[0] && a.cur[1] == b.cur[1] && a.cur[2] == b.cur[2]);
}
int main()
{
    int t,res;
    StateNode b,e;
    cin>>t;
    while(t--){
        res=-1;
        while(!q.empty()){//清空隊列
            q.pop();
        }
        cin>>b.v[0]>>b.v[1]>>b.v[2];
        //下面開始模擬倒水，並搜索
        b.cur[0]=b.v[0];//首先先給最大的水杯倒滿水
        b.cur[1]=b.cur[2]=0;//小杯子為0
        b.step=0;//記錄步數

        cin>>e.cur[0]>>e.cur[1]>>e.cur[2];

        int ok=0;//記錄是否可以到達結尾狀態
        memset(vis,0,sizeof(vis));
        q.push(b);//加入隊列
        vis[b.cur[0]][b.cur[1]][b.cur[2]]=1;//已經在訪問或者已經訪問
        while(!q.empty()){//進行廣搜
            StateNode u=q.front();
            //cout<

C++入門知識

VS2010編寫動態鏈接庫DLL及單元測試用例，調用DLL測試正確性

本文將創建一個簡單的動態鏈接庫，並編寫一個控制台應用程

基礎備忘：函數模板在數組中的使用

函數模板在實際程序中應用比較廣泛，這是由於它本身的特性

POJ 3122 Pie 二分答案

Pie Time Limit: 1000M

vs2008 edit spin 十六進制實現

CodeForces 23D Tetragon 給定凸四邊形3條同邊長的中點求4個頂點計算幾何

題目鏈接：點擊打開鏈接題意：給定3個二維平面上

SendMessage原理初探

今天跟蹤一下SendMessage的實現。用向導先創建一個