Problem A: 走迷宫问题

时间:2022-08-26 20:50:15

Problem A: 走迷宫问题
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 9 Solved: 3
[Submit][Status][Web Board]
Description
给定一个二维数组 int map[5][5] = {
0 , 1 , 0 , 0 , 0 ,
0 , 1 , 0 , 1 , 0 ,
0 , 0 , 0 , 0 , 0 ,
0 , 1 , 1 , 1 , 0 ,
0 , 0 , 0 , 1 , 0 ,
} ;

Input
输入两个正整数m,n 代表m行,n列的矩阵
输入m*n矩阵元素,它表示一个迷宫,其中“1”表示墙壁,“0”表示可以走的路,只能横着走或者竖着走,不能斜着走

Output
要求编写程序求出从左上角到右下角的最短路径的长度,

Sample Input
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
8
my answer:

#include<iostream>
#include<queue>
using namespace std;
typedef struct dot{
int x,y;
int step;
}dot;
int n,m;
bool in(int x,int y)
{
if(x>=&&x<n&&y>=&&y<m)
return true;
else
return false;
}
int dx[]={,,-,};
int dy[]={,,,-}; int main()
{
while(cin>>n>>m){
int vis[][];
for(int i=;i!=n;i++){
for(int j=;j!=m;j++){
cin>>vis[i][j];
}
}
dot g1,next;
int ok=;
g1.x=;
g1.y=;
g1.step=;
queue<dot> q;
// while(!q.empty()) q.pop;
q.push(g1);
int count=;
while(!q.empty()){
dot g;
g=q.front();q.pop();
for(int k=;k<=;k++){
next.x=g.x+dx[k];
next.y=g.y+dy[k];
next.step=g.step+;
if(in(next.x,next.y)&&!vis[next.x][next.y]){
if(next.x==n-&&next.y==m-){
cout<<next.step<<endl;
count++;
ok=;
break;
}
else{
vis[next.x][next.y]=;
q.push(next);
count++;
}
}
}
if(ok)break;
}
if(count==)
cout<<<<endl;
}
return ;
}

Problem A: 走迷宫问题的更多相关文章

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

    走迷宫 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_ 题目描述 一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m) ...

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

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

  3. 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 ...

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

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

  5. C语言动态走迷宫

    曾经用C语言做过的动态走迷宫程序,先分享代码如下: 代码如下: //头文件 #include<stdio.h> #include<windows.h>//Sleep(500)函 ...

  6. 洛谷P1238 走迷宫

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

  7. BZOJ 2707&colon; &lbrack;SDOI2012&rsqb;走迷宫&lpar; tarjan &plus; 高斯消元 &rpar;

    数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了. E(u) = 1 + Σ E(v) / degree(u) 对拍时发现网上2个程序的INF判断和我不一 ...

  8. BZOJ 2707&colon; &lbrack;SDOI2012&rsqb;走迷宫 &lbrack;高斯消元 scc缩点&rsqb;

    2707: [SDOI2012]走迷宫 题意:求s走到t期望步数,\(n \le 10^4\),保证\(|SCC| \le 100\) 求scc缩点,每个scc高斯消元,scc之间直接DP 注意每次清 ...

  9. P1238 走迷宫

    原题链接 https://www.luogu.org/problemnew/show/P1238 为了巩固一下刚学习的广搜,练一下迷宫类型的题 不过这道题我用的深搜..... 看问题,我们就知道这道题 ...

随机推荐

  1. SEO之title优化

    作者:andyrat,联系方式:andyrat@qq.com

  2. ubuntu14&period;04禁用自动待机保持屏幕亮度

    http://jingyan.baidu.com/article/9989c7461fd041f648ecfe05.html

  3. jQuery学习笔记(一):入门

      jQuery学习笔记(一):入门 一.JQuery是什么 JQuery是什么?始终是萦绕在我心中的一个问题: 借鉴网上同学们的总结,可以从以下几个方面观察. 不使用JQuery时获取DOM文本的操 ...

  4. iOS开发-- 利用AVPlayer播放远程音乐和视频

    一.简单的播放音乐和视频,播放视频的工具栏需要自己写 二.利用老师封装的框架实现视频播放 链接:http://pan.baidu.com/s/1hrEKlus 密码:8e7g

  5. CmdBuild

    cmdBuild官网地址:http://www.cmdbuild.org/it 下载.功能和安装说明:http://www.cmdbuild.org/en/download 扩展组件: shark-c ...

  6. 物料分类账 &lbrack;COML&rsqb; PART 1 - 概览

    物料分类账 [COML] PART 1 - 概览 一).原理 1). •实际成本/物料分类帐是产品成本控制模块的一个子模块,产品成本控制包括三个子模块,产品成本计划,成本对象控制,实际成本/物料分类帐 ...

  7. 在英文 sql2005中 比较nvarchar 与 varchar的速度

    declare @str1 varchar(max); declare @count int; ; print 'begin' begin set @str1 = @str1 + '*'; ; end ...

  8. Java基础知识强化95:Calendar类之Calendar类的add&lpar;&rpar;和set&lpar;&rpar;方法

    1. Calendar的add()和set()方法: public void add(int field,int amount):根据给定的日历字段和对应的时间,来对当前的日历进行操作 public ...

  9. unigui 调用js

    //引用单元uniguiapplicationUniSession.AddJS('alert(unigui调用了JS方法)');

  10. JavaScript——语法与数据类型

    严格模式 ECMA5引入了严格模式的概念.严格模式是为JavaScript定义了一种不同的解析与执行模型.在严格模式下,ECMA3中的一些不确定的行为将得到处理,而且对某些不安全的操作也会抛出错误.要 ...