[廣度優先搜索]USACO Feb07 Bronze 青銅蓮花池 Bronze Lilypad (bronlily) 解題報告

譯 By CmYkRgB123

【題目描述】

Farmer John 建造了一個美麗的池塘，用於讓他的牛們審美和鍛鍊。這個長方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有驚人的堅固的蓮花，還有一些岩石，其餘的只是美麗，純淨，湛藍的水。

貝茜正在練習芭蕾舞，她從一個蓮花跳躍到另一個蓮花，當前位於一個蓮花。她希望在蓮花上一個一個的跳，目標是另一個給定蓮花。她能跳既不入水，也不到一個岩石上。

令門外漢驚訝的是，貝茜的每次的跳躍像國際象棋中的騎士一樣：橫向移動M1(1 ≤M1 ≤ 30 )，縱向移動然後量M2 (1 ≤M2 ≤ 30 ;M1 ≠ M2 ) ，或縱向移動然後量M1，橫向移動M2。貝茜有時可能會有多達8個選擇的跳躍。

給定池塘的佈局和貝茜的跳躍格式，請確定貝茜從從她的出發位置，到最終目的地，最小的跳躍次數，貝茜在給出測試數據一定可以跳到目的地。

輸入

第 1 行: 四個用空格隔開的整數: M, N, M1, M2

第 2..M + 1 行: 第 i + 1 行 有 N 個整數，表示該位置的狀態: 0 爲水; 1 爲蓮花; 2 爲岩石; 3 爲貝茜開始的位置; 4 爲貝茜要去的目標位置.

輸出

第 1 行: 一個整數，從起始點到要去的位置，貝茜最小的跳躍次數。

樣例輸入

4 5 1 2

1 0 1 0 1

3 0 2 0 4

0 1 2 0 0

0 0 0 1 0

樣例輸出

2

輸入解釋

貝茜從第2行第1個位置開始，她的目標在第2行最右邊。幾個

輸出解釋

貝茜聰明地跳躍到了第1行第3個位置，然後就到了目的地。

【分析】

這是跳馬問題的變形，但是這個題不能使用深度優先搜索，因為遞歸會爆棧的。我們可以開一個二維的布爾數組，當然整型數組亦可，由於題目中給的岩石和水的作用一樣，直接賦值為false或0，讀入時如果遇到3就記錄下起點的橫縱坐標，如果遇到4就記錄下終點的橫縱坐標，然後把所有的荷花置為true或1。然後處理8種移動方式，可參照2002年NOIP普及組的“過河卒”一題。

接著進行廣度優先搜索，把每一個到過的點全部賦值為false或0，以免重複。還可以加一個剪枝優化：如果當前的跳躍次數不小於已經得到的最優值，直接跳過這個點即可。這樣，就可以把時間複雜度壓得很低了。

 我的測評結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...

编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	7	0.000 s	58877 KB	0
2	正确	7	0.000 s	58877 KB	0
3	正确	7	0.001 s	58877 KB	0
4	正确	7	0.001 s	58877 KB	0
5	正确	7	0.001 s	58877 KB	0
6	正确	7	0.000 s	58877 KB	0
7	正确	7	0.000 s	58877 KB	0
8	正确	7	0.000 s	58877 KB	0
9	正确	7	0.000 s	58877 KB	0
10	正确	7	0.000 s	58877 KB	0
11	正确	7	0.000 s	58877 KB	0
12	正确	7	0.000 s	58877 KB	0
13	正确	7	0.000 s	58877 KB	0

运行完成

运行时间 0.005 s

平均内存使用 58877 KB

测试点通过状况 AAAAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class BRON
{
public:
    int x;
    int y;
    int t;
};

int mat[50][50];
int step[9][2];
int S=0x7fffffff;
int M,N,M1,M2;
int Sx,Sy;
int Ex,Ey;
bool flag[31][31];


void init()
{
    scanf("%d %d %d %d",&M,&N,&M1,&M2);
   
    for (int i=1;i<=M;i++)
        for (int j=1;j<=N;j++)
            flag[i][j]=true;
   
    int tmp;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=N;j++)
        {
            scanf("%d",&tmp);
            if(tmp==0 || tmp==2)
                mat[i][j]=0;
            else
                mat[i][j]=tmp;
            if(mat[i][j]==3)
            {
                Sx=i;
                Sy=j;
                continue;
            }
            if(mat[i][j]==4)
            {
                Ex=i;
                Ey=j;
                continue;
            }
        }
    }
    step[1][0]=M1,step[1][1]=M2;
    step[2][0]=M1,step[2][1]=-M2;
    step[3][0]=-M1,step[3][1]=M2;
    step[4][0]=-M1,step[4][1]=-M2;
    step[5][0]=M2,step[5][1]=M1;
    step[6][0]=M2,step[6][1]=-M1;
    step[7][0]=-M2,step[7][1]=M1;
    step[8][0]=-M2,step[8][1]=-M1;
    return;
}

BRON Q[5000000];
void bfs()
{
    int q=1;
    int h=0;
    Q[0].x=Sx,Q[0].y=Sy,Q[0].t=0;
    int Tx,Ty,Tt;
    int Nx,Ny;
    while(h<q)
    {
        Tx=Q[h].x,Ty=Q[h].y,Tt=Q[h].t;
       
        if(Tx==Ex && Ty==Ey)
        {
            if(Tt<S)
                S=Tt;
            h++;
            continue;
        }
       
        if(Tt>=S)
        {
            h++;
            continue;
        }
       
        if(!flag[Tx][Ty])
        {
            h++;
            continue;
        }
       
        flag[Tx][Ty]=false;
       
        for (int i=1;i<=8;i++)
        {
            Nx=step[i][0]+Tx;
            Ny=step[i][1]+Ty;
            if(Nx>=1 && Nx<=M && Ny>=1 && Ny<=N && flag[Nx][Ny])
            {
                if(mat[Nx][Ny]!=0)
                {
                    Q[q].x=Nx;
                    Q[q].y=Ny;
                    Q[q].t=Tt+1;
                    q++;
                }
            }
        }
        h++;
    }
    cout<<S<<endl;
}

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