[搜索]POI1997 阿里巴巴 ali 解題報告

【問題描述】
想要“芝麻開門”，必須擁有一定數量的錢幣，其中包括至少z枚金幣，s枚銀幣和m枚銅幣。 最初，阿里巴巴擁有三種錢幣若干枚。他可以按照一定規則和芝麻之門的守護者進行交易。 每一種規則用以下形式表示：

z1, s1, m1 -> z2, s2, m2 (zi, si, mis屬於集合{0,1,2,3,4})。

這樣一種規則表示阿里巴巴可以將z1枚金幣, s1枚銀幣, m1枚銅幣換成z2枚金幣, s2枚銀幣, m2枚銅幣。 一次交易而得的錢幣可以繼續參加下一次的交易。

任務

從文件中讀入幾組資料；對於每一組資料：

阿里巴巴最初擁有的金銀銅三種錢幣數目

“芝麻開門”所需的金銀銅三種錢幣數目

所有交易規則

對每一組資料，判斷是否存在有限次的交易，使阿里巴巴能開啟芝麻之門。如果是，則將最少交易次數輸出，否則在輸出NIE(波蘭文NO)

把結果寫進文件中

 

【輸入格式】

文件的第一行有一個整數d<=10,表示資料的組數。

接下來是d組資料，每組佔若干行。

第一行是三個數zp, sp, mp ，屬於集合{0,1,2,3,4}。表示阿里巴巴最初擁有的金銀銅數目。

第二行是三個數z, s, m ， 屬於集合{0,1,2,3,4}。表示芝麻開門所需的金銀銅數目。

第三行是規則總數r，1<=r<=10。

以下r行每行有六個數z1, s1, m1, z2, s2, m2 ，屬於集合{0,1,2,3,4}。表示一種簡單的交易z1, s1, m1 -> z2, s2, m2。

數字之間由若干個空格隔開。

【輸出格式】

文件的第i行為第i組資料的答案：

一個非負整數——阿里巴巴要開啟芝麻之門所需的最少交易次數，或者

單詞NIE(波蘭文NO)

【樣例輸入】

2

2 2 2

3 3 3

3

4

1 0 0 0 1 0

0 1 0 0 0 1

0 0 1 1 0 0

2 0 0 0 2 2

【樣例輸出】

NIE

9

【分析】

搜索+哈希判重，別的也沒有什麼了～由於題目說“開啟芝麻之門所需的最少交易次數”，所以要用廣度優先搜索即BFS實現。  為了防止不必要的交易無限進行下去，可以給每種鑰匙設個上限，如10倍的目標狀態，即如果某個鑰匙的個數大於目標狀態的10倍就停止繼續擴展了。

每搜索一次只要判斷當前狀態的三種鑰匙數是否大於等於目標狀態的鑰匙數即可。

【我的代碼】

查看裸代碼

C++语言: Codee#25241

001 /*
002 *Problem: POI1997 ali
003 *Author: Yeefan
004 *Email: admin@yeefanblog.tk
005 *Website: http://blog.yeefanblog.tk/
006 */
007 #include <cstdio>
008 #include <cstdlib>
009 #include <cstring>
010 #include <queue>
011 #include <iostream>
012 using namespace std;
013
014 const int MAX=10;
015 const int MAXN=5;
016 int N;
017 int R;
018 class AliKey
019 {
020 public:
021     int Gold,Silv,Bron;
022 };
023
024 queue<AliKey>Q;
025 queue<int>Step;
026    
027 AliKey Start,Goal;
028 AliKey Chan1[11];
029 AliKey Chan2[11];
030
031 bool Hash[MAX*MAXN][MAX*MAXN][MAX*MAXN];
032 int Ans;
033
034 void init();
035 void bfs();
036
037 void init()
038 {
039     scanf("%d\n",&N);
040     for (int i=1;i<=N;i++)
041     {
042         scanf("%d %d %d\n",&Start.Gold,&Start.Silv,&Start.Bron);
043         scanf("%d %d %d\n",&Goal.Gold,&Goal.Silv,&Goal.Bron);
044         scanf("%d\n",&R);
045         for (int j=1;j<=R;j++)
046         {
047             scanf("%d %d %d",&Chan1[j].Gold,&Chan1[j].Silv,&Chan1[j].Bron);
048             scanf("%d %d %d\n",&Chan2[j].Gold,&Chan2[j].Silv,&Chan2[j].Bron);
049         }
050        
051         Ans=1000;
052         for (int j1=0;j1<=49;j1++)
053             for (int j2=0;j2<=49;j2++)
054                 for (int j3=0;j3<=49;j3++)
055                     Hash[j1][j2][j3]=false;
056                
057         bfs();
058         if(Ans==1000)
059             printf("NIE\n");
060         else
061             printf("%d\n",Ans);
062     }
063 }
064
065 bool CheckOK(AliKey Tmp,AliKey Chan)
066 {
067     if(Tmp.Gold>=Chan.Gold && Tmp.Silv>=Chan.Silv && Tmp.Bron>=Chan.Bron)
068         return true;
069     return false;
070 }
071
072 bool CheckHashed(AliKey Tmp)
073 {
074     return Hash[Tmp.Gold][Tmp.Silv][Tmp.Bron];
075 }
076
077 void Hashed(AliKey Tmp)
078 {
079     Hash[Tmp.Gold][Tmp.Silv][Tmp.Bron]=true;
080     return;
081 }
082
083 void bfs()
084 {
085     while(!Q.empty())
086         Q.pop();
087     while(!Step.empty())
088         Step.pop();
089    
090     Q.push(Start);
091     Step.push(0);
092     AliKey Tmp;
093     AliKey Next;
094     int ts;
095     Hashed(Start);
096    
097     while(!Q.empty())
098     {
099         Tmp=Q.front();
100         Q.pop();
101         ts=Step.front();
102         Step.pop();
103         
104         if(CheckOK(Tmp,Goal))
105         {
106             Ans=ts;
107             return;
108         }
109        
110         for (int i=1;i<=R;i++)
111         {
112             if(CheckOK(Tmp,Chan1[i]))
113             {
114                 Next.Gold=Tmp.Gold-Chan1[i].Gold+Chan2[i].Gold;
115                 Next.Silv=Tmp.Silv-Chan1[i].Silv+Chan2[i].Silv;
116                 Next.Bron=Tmp.Bron-Chan1[i].Bron+Chan2[i].Bron;
117                 if(CheckHashed(Next))
118                     continue;
119                 if(Next.Gold>(Goal.Gold*MAX) || Next.Silv>(Goal.Silv*MAX)  || Next.Bron>(Goal.Bron*MAX))
120                     continue;
121                 Q.push(Next);
122                 Step.push(ts+1);
123                 Hashed(Next);
124             }
125         }
126     }
127 }
128
129 int main()
130 {
131     freopen("ali.in","r",stdin);
132     freopen("ali.out","w",stdout);
133     init();
134     return 0;
135 }
136
137 /******************************
138 *Result:Accepted
139 *Time:0.007 s
140 *Memory:396 KB
141 ******************************/