走迷宫
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_
题目描述
一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每个格子至多一次的走法数。
输入
对于每组测试数据:
第一行两个整数n, m,表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行,每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走,否则是1 表示这个格子不能走,输入保证起点和终点都是都是可以走的。
任意两组测试数据间用一个空行分开。
输出
示例输入
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应用】的更多相关文章
-
数据结构之 栈与队列--- 走迷宫(深度搜索dfs)
走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方 ...
-
noj电子老鼠走迷宫(深搜dfs)超时错误
1042.电子老鼠闯迷宫 时限:1000ms 内存限制:10000K 总时限:3000ms 描述 有一只电子老鼠被困在如下图所示的迷宫中.这是一个12*12单元的正方形迷宫,黑色部分表示建筑物,白色 ...
-
SDUT 1269 走迷宫(BFS)
点我看题目 题意:中文不详述. 思路 :上上上场比赛让一个BFS给虐了,上次比赛让一个三维的给废掉了.......所以急于从水题刷起......还因为数组开小了WA了5,6次 #include < ...
-
NYOJ306 走迷宫(dfs+二分搜索)
题目描写叙述 http://acm.nyist.net/JudgeOnline/problem.php?pid=306 Dr.Kong设计的机器人卡多非常爱玩.它经常偷偷跑出实验室,在某个游乐场玩之不 ...
-
HDU 2102 A计划(BFS/DFS走迷宫)
A计划 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submis ...
-
百炼3752:走迷宫--栈实现dfs
3752:走迷宫 总时间限制: 1000ms 内存限制: 65536kB 描述 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走:有的格子是空地,可以走.给定一个迷宫,求从左上角走到右下角最 ...
-
SDUT-2449_数据结构实验之栈与队列十:走迷宫
数据结构实验之栈与队列十:走迷宫 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 一个由n * m 个格子组成的迷宫,起 ...
-
LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?
本文始发于个人公众号:TechFlow,原创不易,求个关注 今天是LeetCode专题第48篇文章,我们一起来看看LeetCode当中的第79题,搜索单词(Word Search). 这一题官方给的难 ...
-
洛谷P1238 走迷宫
洛谷1238 走迷宫 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个 ...
随机推荐
-
nios II--实验2——led硬件部分
Led 硬件开发 新建原理图 1.打开Quartus II 11.0,新建一个工程,File -> New Project Wizard…,忽略Introduction,之间单击 Next> ...
-
The finnacial statements,taxes and cash flow
This chapter-2 we learn about the the financial statements(财务报表),taxes and cash flow.We must pay par ...
-
js下读取input中的value值
很多人(包括我),总想像以前操作js一样,读取到input中的值:document.getElementById('').value; 结果事实证明这样读到得是null. eval(document. ...
-
vue 高德地图之玩转周边
前言:在之前的博客中,有成功引入高德地图,这是以前的地址 vue 调用高德地图. 因为一些需求,需要使用到地图的周边功能. 完整的项目代码请查看 我的github 一 .先看要实现的结果,参考了链 ...
-
jqueryEasyUI列表
背景 因为学习大数据开发这段时间,同时也学习java的一些知识.利用了近五个月的时间来投入学习,当然我选择了一个机构,因为已经做了四年多的开发,所以即使不是做的java但是java还是了解的,这段时间 ...
-
Eclipse新建动态页面
作为web小学生,写一下很多人问的基本基本基本问题 新建web项目 出现一下界面: 明明完成后一直点击next,但不要点击finish 知道出现这个界面(最后一个界面) 打上勾(用来自动生成web.x ...
-
GitHub下载单个文件
1. 点击某个文件. 2. 右键点击RAW. 3. 另存为
-
分部类,分部方法 - 修饰符partial
一.分部类 什么是部分类呢?简单来说就是将一个类型或方法拆分到两个或多个源文件中,每个源文件只包含类型定义的一部分. 当使用自动生成的源时,无须重新创建源文件便可将代码添加到类中.Visual Stu ...
-
【Java】 剑指offer(45) 把数组排成最小的数
本文参考自<剑指offer>一书,代码采用Java语言. 更多:<剑指Offer>Java实现合集 题目 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接 ...
-
【命令】MongoDB常用命令记录
如果你想创建一个“myTest”的数据库,先运行use myTest命令,之后就做一些操作(如:db.createCollection('user')),这样就可以创建一个名叫“myTest”的数据库 ...