Pots【廣搜,模擬】

Pots

?POJ - 3414?

You are given two pots, having the volume of?A?and?B?liters respectively. The following operations can be performed:

  1. FILL(i)??????? fill the pot?i?(1 ≤?i?≤ 2) from the tap;
  2. DROP(i)????? empty the pot?i?to the drain;
  3. POUR(i,j)??? pour from pot?i?to pot?j; after this operation either the pot?jis full (and there may be some water left in the pot?i), or the pot?i?is empty (and all its contents have been moved to the pot?j).

Write a program to find the shortest possible sequence of these operations that will yield exactly?C?liters of water in one of the pots.

Input

On the first and only line are the numbers?A,?B, and?C. These are all integers in the range from 1 to 100 and?C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations?K. The following?K?lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

題意:給你三個數字A,B,C,A,B代表容器的體積,C代表需要得到的水的體積,每次可以進行六種操作:將A容器填滿;將B容器填滿:將A容器的水倒入B中;將B容器的水倒入A中;倒掉A中的水;倒掉B中的水。問最少需要多少步才能夠使A,B中某容器的水恰好為C升,并將過程輸出。

方法:通過廣搜每次遍歷六種情況,記錄其前一個步驟,再通過深搜輸出,博主代碼過于冗長,望見諒!!!

AC代碼:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e6 + 5;
const ll mod = 1e9+7;
int a,b,a1,b1,c;
struct node
{int x,y;int step;int pre;int id;int way;
};
int ids;
int tpl;
bool vis[1000][1000];
int tmp[maxn];
int tmp1[maxn];
int bfs()
{node no;no.x=0;no.y=0;vis[0][0]=true;no.pre=-1;no.step=0;no.way=-1;no.id=0;tmp[no.id]=no.pre;tmp[no.id]=no.way;ids=0;queue<node> q;while(!q.empty())q.pop();q.push(no);while(!q.empty()) {node front=q.front();q.pop();for(int i=1;i<=6;i++){node tail;switch(i) {case 1:{if(front.x<a&&vis[a][front.y]==false){tail.x=a;tail.y=front.y;tail.step=front.step+1;ids++;tail.id=ids;tail.pre=front.id;tail.way=1;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;vis[a][front.y]=true;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}break;}case 2:{if(front.y<b&&vis[front.x][b]==false){tail.y=b;tail.x=front.x;ids++;tail.id=ids;tail.step=front.step+1;tail.pre=front.id;tail.way=2;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;vis[front.x][b]=true;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}break;}case 3:{if(front.x>0&&front.y<b){int k1=front.x-(b-front.y),k2;if(k1<0){k1=0;k2=front.y+front.x;}else{k1=front.x-(b-front.y);k2=b;}if(vis[k1][k2]==false){vis[k1][k2]=true;tail.x=k1;tail.y=k2;ids++;tail.id=ids;tail.step=front.step+1;tail.pre=front.id;tail.way=3;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}}break;}case 4:{if(front.y>0&&front.x<a){int k1=front.y-(a-front.x),k2;if(k1<0){k1=0;k2=front.x+front.y;}else{k1=front.y-(a-front.x);k2=a;}if(vis[k2][k1]==false){vis[k2][k1]=true;tail.y=k1;tail.x=k2;ids++;tail.id=ids;tail.step=front.step+1;tail.pre=front.id;tail.way=4;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}}break;}case 5:{if(front.x>0&&vis[0][front.y]==false){vis[0][front.y]=true;tail.x=0;tail.y=front.y;ids++;tail.id=ids;tail.step=front.step+1;tail.pre=front.id;tail.way=5;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}break;}case 6:{if(front.y>0&&vis[front.x][0]==false){vis[front.x][0]=true;tail.x=front.x;tail.y=0;ids++;tail.id=ids;tail.step=front.step+1;tail.pre=front.id;tail.way=6;tmp[tail.id]=tail.pre;tmp1[tail.id]=tail.way;if(tail.x==c||tail.y==c){tpl=tail.id;return tail.step;}q.push(tail);//printf("%d-----%d %d\n",tail.way,tail.x,tail.y);}break;}default :break;}//printf("----------------%d\n",i);}}return -1;
}
void dfs(int x)
{if(tmp[tmp[x]]!=-1)dfs(tmp[x]);switch(tmp1[x]){case 1:{printf("FILL(1)\n");break;}case 2:{printf("FILL(2)\n");break;}case 3:{printf("POUR(1,2)\n");break;}case 4:{printf("POUR(2,1)\n");break;}case 5:{printf("DROP(1)\n");break;}case 6:{printf("DROP(2)\n");break;}default :{break;}}
}int main() 
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);scanf("%d %d %d",&a,&b,&c);int ans=bfs();if(ans==-1)printf("impossible\n");else{printf("%d\n",ans);dfs(tpl);}return 0;
}

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/536376.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/536376.shtml
英文地址,請注明出處:http://en.pswp.cn/news/536376.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

非常可樂【廣搜,模擬】

非常可樂 HDU - 1495 大家一定覺的運動以后喝可樂是一件很愜意的事情&#xff0c;但是seeyou卻不這么認為。因為每次當seeyou買了可樂以后&#xff0c;阿牛就要求和seeyou一起分享這一瓶可樂&#xff0c;而且一定要喝的和seeyou一樣多。但seeyou的手中只有兩個杯子&#xff0…

問題 A: 深度學習

問題 A: 深度學習 時間限制: 1 Sec 內存限制: 128 MB 提交: 53 解決: 42 [提交] [狀態] [討論版] [命題人:admin] 題目描述 小 A 最近在研究深度學習&#xff0c;他自己搭建了一個很牛逼的神經網絡&#xff0c;現在他手頭一共有 n 組訓練數據&#xff0c;一開始他會給自己的…

堆樹

一、堆樹的定義 堆樹的定義如下&#xff1a; &#xff08;1&#xff09;堆樹是一顆完全二叉樹&#xff1b; &#xff08;2&#xff09;堆樹中某個節點的值總是不大于或不小于其孩子節點的值&#xff1b; &#xff08;3&#xff09;堆樹中每個節點的子樹都是堆樹。 當父節點的鍵…

問題 D: 最小生成樹II

問題 D: 最小生成樹II 時間限制: 1 Sec 內存限制: 128 MB 提交: 89 解決: 44 [提交] [狀態] [討論版] [命題人:admin] 題目描述 小A有一張n個點的帶權無向圖&#xff0c;這張無向圖非常特別&#xff0c;首先第i個點有一個點權ai&#xff0c;之后這張無向圖是一張完全圖&…

問題 G: 區間權值

問題 G: 區間權值 時間限制: 1 Sec 內存限制: 128 MB 提交: 112 解決: 49 [提交] [狀態] [討論版] [命題人:admin] 題目描述 小Bo有n個正整數a1..an&#xff0c;以及一個權值序列w1…wn&#xff0c;現在他定義 現在他想知道的值&#xff0c;需要你來幫幫他 你只需要輸出答案…

問題 I: 連通塊計數

問題 I: 連通塊計數 時間限制: 1 Sec 內存限制: 128 MB 提交: 108 解決: 45 [提交] [狀態] [討論版] [命題人:admin] 題目描述 小A有一棵長的很奇怪的樹&#xff0c;他由n條鏈和1個點作為根構成&#xff0c;第i條鏈有ai個點&#xff0c;每一條鏈的一端都與根結點相連。 現在…

telnet 功能啟用并測試端口是否正常

記錄日期&#xff1a;2019年6月21日 13點52分 操作系統&#xff1a;Windows 10 由于 Ping命令可以檢查網絡是否連通&#xff0c;但無法準確判斷某個端口是否連通&#xff0c;因此需要使用 Telnet協議。 1、打開控制面板中的程序和功能。 2、側邊欄&#xff0c;啟用或關閉Window…

步步為營 SharePoint 開發學習筆記系列 七、SharePoint Timer Job 開發

概要 項目需求要求我們每天晚上同步員工的一些信息到sharepoint 的user List &#xff0c;我們決定定制開發sharepoint timer Job,Sharepoint timer Job是sharePoint的定時作業Job,需要安裝、布曙到服務器上,而這里我只是介紹下Job開發的例子&#xff0c;以供大家學習用。 開發…

問題 J: 尋找復讀機【模擬】

問題 J: 尋找復讀機 時間限制: 1 Sec 內存限制: 128 MB 提交: 131 解決: 50 [提交] [狀態] [討論版] [命題人:admin] 題目描述 某個QQ群里一共有n個人&#xff0c;他們的編號是1..n&#xff0c;其中有一些人本質上是復讀機。 小A發現&#xff0c;如果一個人的本質是復讀機&…

windows下jenkins常見問題填坑

沒有什么高深的東西&#xff0c;1 2天的時間大多數人都能自己摸索出來&#xff0c;這里將自己遇到過的問題分享出來避免其他同學再一次挖坑. 目錄 1. 主從節點 2. Nuget自動包還原 3. powershell部署 4. 內網機器實現基于變化的構建 5. Github私有項目pull時限 所謂主從&#x…

Cow Contest【最短路-floyd】

Cow Contest POJ - 3660 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors. …

【學習Android NDK開發】Type Signatures(類型簽名)

類型簽名&#xff08;Type Signatures&#xff09; (<Parameter 1 Type Code>[<Parameter 1 Class>];...)<Return Type Code> The JNI uses the Java VM’s representation of type signatures. Following Table shows these type signatures. Type Signatur…

Symantec(賽門鐵克)非受管檢測

為了查找局域網內沒有安裝賽門鐵克客戶端的IP&#xff0c;采用Symantec Endpoint Protect Manager 的非受管檢測機制進行網段掃描。 非受管檢測機制的原理是&#xff1a;每臺電腦開機時都會向同網段電腦發arp&#xff0c;當非受管檢測器接到arp請求時&#xff0c;會寫入本地的a…

SQL語句性能優化操作

1、對查詢進行優化&#xff0c;應盡量避免全表掃描&#xff0c;首先應考慮在where及order by涉及的列上建立索引。 2、應盡量避免在where子句中對字段進行null值判斷&#xff0c;創建表時NULL是默認值&#xff0c;但大多數時候應該使用NOT NULL&#xff0c;或者使用一個特殊的值…

sql語言特殊字符處理

我們都知道SQL Server查詢過程中&#xff0c;單引號“”是特殊字符&#xff0c;所以在查詢的時候要轉換成雙單引號“”。但這只是特殊字符的一個&#xff0c;在實際項目中&#xff0c;發現對于like操作還有以下特殊字符&#xff1a;下劃線“_”&#xff0c;百分號“%”&#xf…

小節

算法導論已學兩部分&#xff0c;第一部分是基礎知識&#xff0c;第二部分是排序。基礎知識介紹如何分析證明算法以及求時間復雜度。第二部分的排序學了很長時間。先是從簡單排序到復雜排序的一個過渡&#xff0c;打開了很多思路。然后就是無盡的算法分析。算法分析的時間比理解…

SPS2003升級到MOSS2007相關資料及問題總結

這幾天要把客戶的SPS2003門戶升級到MOSS2007的&#xff0c;客戶SPS2003門戶&#xff0c;數據26G&#xff0c;使用了自定義WebPart、自定義頁面、SSO等功能。升級過程中碰到大量問題。其中主要的問題有幾個&#xff0c;在這里把它們整理一下> 1、sps2003升級時&#xff0c;升…

Milking Time【動態規劃-dp】

Milking Time POJ - 3616 Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0..N-1) so that she produces as much milk as po…

HTTP首部(1)

1、報文首部 HTTP協議的請求和響應必定包含HTTP首部&#xff0c;它包括了客戶端和服務端分別處理請求和響應提供所需要的信息。報文主體字兒是所需要的用戶和資源的信息都在這邊。  HTTP請求報文組成 方法&#xff0c;URL&#xff0c;HTTP版本&#xff0c;HTTP首部字段 HTTP響…

UVA272--TEX Quotes【字符串】

TEX Quotes UVA - 272 題目傳送門 題目大意&#xff1a;將輸入字符串中的所有對雙引號的做雙引號改為 &#xff0c;右雙引號改為 。 解決方法&#xff1a;遍歷一遍及時修改即可。 AC代碼&#xff1a; #include <cstdio> #include <iostream> #include <…