原题链接 https://www.luogu.org/problemnew/show/P1238
为了巩固一下刚学习的广搜,练一下迷宫类型的题 不过这道题我用的深搜.....
看问题,我们就知道这道题和平时做的走迷宫的题差不多,只是把方案数改成了输出路径
那也很好办,我们只要记录一下每一步的坐标,如果到了终点就输出记录下来的坐标就好了
注意题目中给出的优先顺序:左上右下 表示被坑了一次qaq
给出AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[][];
int dx[]={,-,,},dy[]={-,,,}; //注意题目中给出的顺序!!! 优先顺序:左上右下
int sx,sy,fx,fy,flag=,t; //sx,sy表示起点横纵坐标,fx,fy表示终点横纵坐标
bool vis[][]; //判断是否到达过
bool map[][]; //地图
void search(int x,int y)
{
if(x==fx&&y==fy) //判断是否到终点
{
for(int j=;j<=t;j++)
printf("(%d,%d)->",a[j][],a[j][]); //输出路径
printf("(%d,%d)\n",fx,fy);
flag=; //标记为有解
}
for(int i=;i<;i++) //四个方向
{
if(map[x+dx[i]][y+dy[i]]==&&vis[x+dx[i]][y+dy[i]]==&&x+dx[i]>=&&x+dx[i]<=n&&y+dy[i]>=&&y+dy[i]<=m)
//判断是否在界内,以及该点是否到过和是否能走
{
t++; //步数+1
vis[x][y]=; //标记为1,表示该点已经走过
a[t][]=x; //记录横坐标
a[t][]=y; //记录纵坐标
search(x+dx[i],y+dy[i]); //深搜的递归思想~,进一步搜索下去
vis[x][y]=; //回溯操作
t--;
}
} }
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>map[i][j];
cin>>sx>>sy;
cin>>fx>>fy;
search(sx,sy); //开始搜索
if(flag==) cout<<"-1"; //如果无解,则输出-1
return ;
}
P1238 走迷宫的更多相关文章
-
洛谷——P1238 走迷宫
P1238 走迷宫 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个数 ...
-
洛谷P1238 走迷宫
洛谷1238 走迷宫 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个 ...
-
洛谷P1238 走迷宫题解
题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个数据来描述的,分别表示 ...
-
洛谷 P1238 走迷宫
因为小处疏漏,多花了半小时的水题 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束 ...
-
luogu P1238 走迷宫--DFS模板好(水)题
题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点.结束点(起始点和结束点都是用两个数据来描述的,分别表示 ...
-
洛谷—— P1238 走迷宫
https://www.luogu.org/problem/show?pid=1238 题目描述 有一个m*n格的迷宫(表示有m行.n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走 ...
-
C语言动态走迷宫
曾经用C语言做过的动态走迷宫程序,先分享代码如下: 代码如下: //头文件 #include<stdio.h> #include<windows.h>//Sleep(500)函 ...
-
sdut 2449走迷宫【最简单的dfs应用】
走迷宫 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_ 题目描述 一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m) ...
-
BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )
数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了. E(u) = 1 + Σ E(v) / degree(u) 对拍时发现网上2个程序的INF判断和我不一 ...
随机推荐
-
HDU2841 Visible Trees(容斥原理)
题目..大概就是有个m*n个点的矩形从(1,1)到(m,n),问从(0,0)出发直线看过去最多能看到几个点. 如果(0,0)->(x,y)和(0,0)->(x',y')两个向量平行,那后面 ...
-
php 缓存加速器软件
Xcache 和 memcached 是两个不同层面的缓存,不存在可比性.Xcache 是 php 底层的缓存,它将PHP程式编译成字节码(byte code),再透过服务器上安装对应的程式来执行PH ...
-
HeadFirst Jsp 11 (部署WEB应用)
web 应用的目录结构要求很严, 各个内容只能放在它该放的地方, 所以, 移动一个web应用很让人头疼. 不过还是有办法, WAR文件, 代表web 归档, WAR其实就是一个JAR归档. 建立 WA ...
-
Sql 函数大全 (更新中...由难到简
1.字符处理类: 1.1 指定指定字符输出的次数 ) 结果:1a1a1a1a1a (5个1a)
- 2008r2 显示桌面图标
-
构建安全的Xml Web Service系列之wse之证书存储位置
原文:构建安全的Xml Web Service系列之wse之证书存储位置 我们在前几天对xml web service的安全性提出了一些建议,大家可以通过以下地址访问: 构建安全的Xml Web Se ...
-
PyTorch入门(一)向量
什么是PyTorch? PyTorch是Facebook人工智能团队开发的一个机器学习和深度学习工具,用于处理大规模图像分析,包括物体检测,分割与分类.但是它的功能不仅限于此.它与其它深度学习框架 ...
-
.net 本地日志的添加
/// <summary> /// 写入日志到文本文件 /// </summary> /// <param name="userName">用户 ...
-
python之+=与+(转载)
先看一个简单的例子 从程序分析,进行直接+操作后,python会重新生成一个对象,而进行+=操作并不改变原来的对象,是在原来对象的基础上进行操作,所以+=也称为就地加 除此之外+和+=还有不同: 从程 ...
-
TF之RNN:matplotlib动态演示之基于顺序的RNN回归案例实现高效学习逐步逼近余弦曲线—Jason niu
import tensorflow as tf import numpy as np import matplotlib.pyplot as plt BATCH_START = 0 TIME_STEP ...