樣例輸入：

2   // 測試數(shù)據(jù)個數(shù)

目前創(chuàng)新互聯(lián)建站已為上千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計、五通橋網(wǎng)站維護等服務(wù)，公司將堅持客戶導向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

6 1 3 // 棋盤大小 蛇的個數(shù) 梯子個數(shù)

35 25  // 蛇的起始位置（蛇頭） 蛇的終止位置（蛇尾）

3 23 5 16 20 33 梯子起始位置（梯子底部） 梯子終止位置（頂部）

樣例輸出：

3

#include <cstdio>
#include<cstring>
#define NMAX  20
#define SLMAX 200

struct SnakeAndLadder  //蛇和梯子{
int from, to;  //起止位置};

int main( )
{
int D;   //測試數(shù)據(jù)的個數(shù)  int N, S, L; //每個測試數(shù)據(jù)中的N、S、L：棋盤規(guī)模、蛇和梯子數(shù)目  int grid[ NMAX*NMAX+1 ];  //棋盤(序號從1開始計)
//備份上一次棋盤狀態(tài)(序號從1開始計)  int gridbak[ NMAX*NMAX+1 ];
    SnakeAndLadder obstacle[2*SLMAX ];  //障礙物，包括梯子和蛇  int i, j, k, m;  //循環(huán)變量  int step;  //投骰子的數(shù)目  int deal;  //如果落腳處是蛇(懲罰)首部或梯子(獎勵)底部，則deal為1    
    scanf("%d", &D );

for( i=0; i<D; i++ )  //處理每個測試數(shù)據(jù)    {
        scanf("%d%d%d", &N, &S, &L );
for( j=0; j<S+L; j++ )
            scanf("%d%d", &obstacle[j].from, &obstacle[j].to );        
        memset( grid,0, sizeof(grid) );  grid[1] = 1;  //初始化狀態(tài)數(shù)組        step = 0;  //初始化骰子數(shù)目
//只要第N^2個方格沒有擴展為1，則繼續(xù)按BFS進行擴展   while( grid[N*N]==0 )
        {
            memcpy( gridbak, grid,sizeof(grid) );//備份上一步棋盤狀態(tài)
//grid[ ]數(shù)組用來保存在上一步棋盤狀態(tài)(graibak[ ])下進行擴展后的狀態(tài)            memset( grid, 0, sizeof(grid) );
//搜索所有的格子,最后一格不用搜索,因為在搜索過程結(jié)束前它一定為0 for( j=1; j<=N*N-1; j++ )
            {
if( gridbak[j]==0 )  //若在上一步無法到達此格則跳過   continue;
//考慮點數(shù)1～6,走該點數(shù)步數(shù)后到達j+k位置  for( k=1; k<=6; k++ )
                {
                    deal= 0;
if( j+k>N*N )break;
for( m=0; m<S+L; m++ )
                    {
//如果j+k位置是某個蛇(或梯子)的起始位置
//則沿著它到達終止位置 if( obstacle[m].from==j+k )
                        {
                            grid[ obstacle[m].to ]= 1;  deal = 1;
break;  //j+k位置上最多只有
//一個蛇(或梯子)的起止位置                        }
                    }
//不利用蛇或梯子   if( deal==0 && grid[j+k]==0 )  grid[j+k] = 1;
                }
            }
            step++;  //骰子數(shù)加一        }
        printf("%d
", step );
    }
return 0;
}

當前標題：蛇跟樓梯(BFS)-創(chuàng)新互聯(lián)
標題URL：http://www.aaarwkj.com/article2/dddcoc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、網(wǎng)站改版、定制網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、手機網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)