sdut 2449走迷宫【最简单的dfs应用】

时间:2022-08-26 20:44:43

走迷宫

Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_

题目描述

一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每个格子至多一次的走法数。

输入

       第一行一个整数T 表示有T 组测试数据。(T <= 110)

对于每组测试数据:

第一行两个整数n, m,表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行,每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走,否则是1 表示这个格子不能走,输入保证起点和终点都是都是可以走的。

任意两组测试数据间用一个空行分开。

输出

 对于每组测试数据,输出一个整数R,表示有R 种走法。

示例输入

3
2 2
0 1
0 0
2 2
0 1
1 0
2 3
0 0 0
0 0 0

示例输出

1
0
4
 #include<iostream>
#include<string.h>
using namespace std;
int visited[][];
int m,n;
int f[][],sum;
int hang[]={,,,-},lie[]={,,-,};
void dfs(int h,int l)
{
visited[h][l]=;
int i;
for(i=;i<=;i++)
{
int h1=h+hang[i];
int l1=l+lie[i];
if(h1>=&&h1<=m&&l1>=&&l1<=n)
{
if(f[h1][l1]==&&visited[h1][l1]!=)
{
if(h1==m&&l1==n)
sum++;
else dfs(h1,l1);
}
}
}
visited[h][l]=;
}
int main()
{
int zong;
cin>>zong;
while(zong--)
{
memset(visited,,sizeof(visited));
memset(f,,sizeof(f));
sum=;
cin>>m>>n;
int i,j;
for(i=;i<=m;i++)
for(j=;j<=n;j++)
cin>>f[i][j];
dfs(,);
cout<<sum<<endl;
}
return ;
}

sdut 2449走迷宫【最简单的dfs应用】的更多相关文章

  1. 数据结构之 栈与队列--- 走迷宫(深度搜索dfs)

    走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方 ...

  2. noj电子老鼠走迷宫(深搜dfs)超时错误

    1042.电子老鼠闯迷宫 时限:1000ms 内存限制:10000K  总时限:3000ms 描述 有一只电子老鼠被困在如下图所示的迷宫中.这是一个12*12单元的正方形迷宫,黑色部分表示建筑物,白色 ...

  3. SDUT 1269 走迷宫(BFS)

    点我看题目 题意:中文不详述. 思路 :上上上场比赛让一个BFS给虐了,上次比赛让一个三维的给废掉了.......所以急于从水题刷起......还因为数组开小了WA了5,6次 #include &lt ...

  4. NYOJ306 走迷宫&lpar;dfs&plus;二分搜索&rpar;

    题目描写叙述 http://acm.nyist.net/JudgeOnline/problem.php?pid=306 Dr.Kong设计的机器人卡多非常爱玩.它经常偷偷跑出实验室,在某个游乐场玩之不 ...

  5. HDU 2102 A计划&lpar;BFS&sol;DFS走迷宫&rpar;

    A计划 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submis ...

  6. 百炼3752&colon;走迷宫--栈实现dfs

    3752:走迷宫 总时间限制:  1000ms 内存限制:  65536kB 描述 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走:有的格子是空地,可以走.给定一个迷宫,求从左上角走到右下角最 ...

  7. SDUT-2449&lowbar;数据结构实验之栈与队列十:走迷宫

    数据结构实验之栈与队列十:走迷宫 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 一个由n * m 个格子组成的迷宫,起 ...

  8. LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?

    本文始发于个人公众号:TechFlow,原创不易,求个关注 今天是LeetCode专题第48篇文章,我们一起来看看LeetCode当中的第79题,搜索单词(Word Search). 这一题官方给的难 ...

  9. 洛谷P1238 走迷宫

    洛谷1238 走迷宫 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个 ...

随机推荐

  1. nios II--实验2——led硬件部分

    Led 硬件开发 新建原理图 1.打开Quartus II 11.0,新建一个工程,File -> New Project Wizard…,忽略Introduction,之间单击 Next&gt ...

  2. The finnacial statements&comma;taxes and cash flow

    This chapter-2 we learn about the the financial statements(财务报表),taxes and cash flow.We must pay par ...

  3. js下读取input中的value值

    很多人(包括我),总想像以前操作js一样,读取到input中的值:document.getElementById('').value; 结果事实证明这样读到得是null. eval(document. ...

  4. vue 高德地图之玩转周边

    前言:在之前的博客中,有成功引入高德地图,这是以前的地址  vue 调用高德地图. 因为一些需求,需要使用到地图的周边功能. 完整的项目代码请查看  我的github 一 .先看要实现的结果,参考了链 ...

  5. jqueryEasyUI列表

    背景 因为学习大数据开发这段时间,同时也学习java的一些知识.利用了近五个月的时间来投入学习,当然我选择了一个机构,因为已经做了四年多的开发,所以即使不是做的java但是java还是了解的,这段时间 ...

  6. Eclipse新建动态页面

    作为web小学生,写一下很多人问的基本基本基本问题 新建web项目 出现一下界面: 明明完成后一直点击next,但不要点击finish 知道出现这个界面(最后一个界面) 打上勾(用来自动生成web.x ...

  7. GitHub下载单个文件

    1. 点击某个文件. 2. 右键点击RAW. 3. 另存为

  8. 分部类,分部方法 - 修饰符partial

    一.分部类 什么是部分类呢?简单来说就是将一个类型或方法拆分到两个或多个源文件中,每个源文件只包含类型定义的一部分. 当使用自动生成的源时,无须重新创建源文件便可将代码添加到类中.Visual Stu ...

  9. 【Java】 剑指offer&lpar;45&rpar; 把数组排成最小的数

    本文参考自<剑指offer>一书,代码采用Java语言. 更多:<剑指Offer>Java实现合集   题目 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接 ...

  10. 【命令】MongoDB常用命令记录

    如果你想创建一个“myTest”的数据库,先运行use myTest命令,之后就做一些操作(如:db.createCollection('user')),这样就可以创建一个名叫“myTest”的数据库 ...