蛇跟楼梯(BFS)-创新互联

样例输入：

2   // 测试数据个数

目前创新互联建站已为上千家的企业提供了网站建设、域名、网页空间、网站托管、企业网站设计、五通桥网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

6 1 3 // 棋盘大小 蛇的个数 梯子个数

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;   //测试数据的个数  int N, S, L; //每个测试数据中的N、S、L：棋盘规模、蛇和梯子数目  int grid[ NMAX*NMAX+1 ];  //棋盘(序号从1开始计)
//备份上一次棋盘状态(序号从1开始计)  int gridbak[ NMAX*NMAX+1 ];
    SnakeAndLadder obstacle[2*SLMAX ];  //障碍物，包括梯子和蛇  int i, j, k, m;  //循环变量  int step;  //投骰子的数目  int deal;  //如果落脚处是蛇(惩罚)首部或梯子(奖励)底部，则deal为1    
    scanf("%d", &D );

for( i=0; i<D; i++ )  //处理每个测试数据    {
        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;  //初始化状态数组        step = 0;  //初始化骰子数目
//只要第N^2个方格没有扩展为1，则继续按BFS进行扩展   while( grid[N*N]==0 )
        {
            memcpy( gridbak, grid,sizeof(grid) );//备份上一步棋盘状态
//grid[ ]数组用来保存在上一步棋盘状态(graibak[ ])下进行扩展后的状态            memset( grid, 0, sizeof(grid) );
//搜索所有的格子,最后一格不用搜索,因为在搜索过程结束前它一定为0 for( j=1; j<=N*N-1; j++ )
            {
if( gridbak[j]==0 )  //若在上一步无法到达此格则跳过   continue;
//考虑点数1～6,走该点数步数后到达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++;  //骰子数加一        }
        printf("%d
", step );
    }
return 0;
}

当前标题：蛇跟楼梯(BFS)-创新互联
标题URL：https://www.cdcxhl.com/article2/dddcoc.html

成都网站建设公司_创新互联，为您提供网站制作、网站改版、定制网站、外贸网站建设、手机网站建设、企业网站制作

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联