[廣度優先搜索]USACO Jan07:The Bale Tower (btwr)解題報告

    The Bale Tower

Always bored with cud-chewing, the cows have invented a new game. One cow retrieves a set of N (3 ≤ N ≤ 20) hay bales from the shed each of which is one unit high. Each bale also has some unique width and unique breadth.
A second cow tries to choose a set of bales to make the tallest stack of bales in which each bale can be placed only on a bale whose own width and breadth are smaller than the width and breadth of the bale below. Bales can not be rotated to interchange the width and breadth.
Help the cows determine the highest achievable tower that can be legally built form a set of bales.
Input

• Line 1: A single integer, N

• Lines 2..N + 1: Each line describes a bale with two space-separated integers,respectively the width and breadth

Output

• Line 1: The height of the tallest possible tower that can legally be built from the bales.

Sample Input

6
6 9
10 12
9 11
8 10
7 8
5 3

Sample Output

5

Input Details Six bales of various widths and breadths
Output Details These bales can be stacked for a total height of 5:

10 12
9 11
8 10
6 9
5 3

[another stacking exists, too]

【分析】
Google翻譯的真扯淡啊～“罷了塔”！ 最後我還是看著英文做出來這道題。

這題明顯是搜索題，我不知道深度優先搜索能否過全，我用的是廣度優先搜索。 一開始，把所有的bale全部加入隊列，然後逐個判斷哪些bale可以放上去，把能放上去的bale加入隊列，直到隊列為空了，輸出最大高度即可。

【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class Bale
{
public:
    int W;
    int B;
}S[21];
int Tot=0;
int N;

class QQ
{
public:
    int A;
    int T;
}Q[10000000];

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
        scanf("%d %d\n",&S[i].W,&S[i].B);
    return;
}

void bfs()
{
    for (int i=1;i<=N;i++)
    {
        Q[i-1].A=i;
        Q[i-1].T=1;
    }
   
    int b=N;
    int s=0;
   
    int Ta;
    int Tw,Tb;
    int Nw,Nb;
   
    while(s<=b)
    {
        Ta=Q[s].A;
        Tw=S[Ta].W;
        Tb=S[Ta].B;
       
        for (int i=1;i<=N;i++)
        {
            if(i==Ta)
                continue;
            Nw=S[i].W;
            Nb=S[i].B;
            if(Nb>=Tb ||  Nw>=Tw)
                continue;
            Q[b].A=i;
            Q[b].T=Q[s].T+1;
            if(Tot<Q[b].T)
                Tot=Q[b].T;
            b++;
        }
        s++;
    }       
    cout<<Tot<<endl;
}

int main()
{
    freopen("btwr.in","r",stdin);
    freopen("btwr.out","w",stdout);
    init();
    bfs();
    return 0;
}