题目:http://poj.org/problem?id=3009
参考博客:http://www.cnblogs.com/LK1994/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<iomanip>
#include<cmath>
#include<map>
#include<vector>
#include<algorithm>
using namespace std; int w,h,G[][];
int d[][]={{,},{,-},{-,},{,}};
int minstep; int dfs(int sx,int sy,int step)
{
if(step>)
return step;
for(int i=; i<; i++)
for(int k=; k<; k++)
{
int tx=sx+d[i][]*k;
int ty=sy+d[i][]*k;
if(tx>=&&tx<=h&&ty>=&&ty<=w)
{
if(G[tx][ty]==) return step+;
else if(G[tx][ty]==)
{
if(k==) break;
int x=sx+d[i][]*(k-);
int y=sy+d[i][]*(k-);
G[tx][ty]=;
minstep=min(minstep,dfs(x,y,step+));
G[tx][ty]=;
break;
}
}
else break;
}
return minstep;
}
int main()
{
int sx,sy,ans;
while(cin>>w>>h&&(w!=||h!=))
{
for(int i=; i<=h; i++)
for(int j=; j<=w; j++)
{
cin>>G[i][j];
if(G[i][j]==)
{
sx=i; sy=j;
G[i][j]=;
}
}
minstep=;
ans=dfs(sx,sy,);
if(ans>) ans=-;
cout<<ans<<endl;
}
return ;
}
poj 3009 Curling 2.0( dfs )的更多相关文章
-
POJ 3009 Curling 2.0(DFS + 模拟)
题目链接:http://poj.org/problem?id=3009 题意: 题目很复杂,直接抽象化解释了.给你一个w * h的矩形格子,其中有包含一个数字“2”和一个数字“3”,剩下的格子由“0” ...
-
POJ 3009 Curling 2.0【带回溯DFS】
POJ 3009 题意: 给出一个w*h的地图,其中0代表空地,1代表障碍物,2代表起点,3代表终点,每次行动可以走多个方格,每次只能向附近一格不是障碍物的方向行动,直到碰到障碍物才停下来,此时障碍物 ...
-
poj 3009 Curling 2.0 (dfs )
Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11879 Accepted: 5028 Desc ...
-
【POJ】3009 Curling 2.0 ——DFS
Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11432 Accepted: 4831 Desc ...
-
POJ 3009 Curling 2.0 {深度优先搜索}
原题 $On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules ...
-
POJ 3009 Curling 2.0 回溯,dfs 难度:0
http://poj.org/problem?id=3009 如果目前起点紧挨着终点,可以直接向终点滚(终点不算障碍) #include <cstdio> #include <cst ...
-
poj 3009 Curling 2.0
题目来源:http://poj.org/problem?id=3009 一道深搜题目,与一般搜索不同的是,目标得一直往一个方向走,直到出界或者遇到阻碍才换方向. 1 #include<iostr ...
-
【原创】poj ----- 3009 curling 2 解题报告
题目地址: http://poj.org/problem?id=3009 题目内容: Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Tot ...
-
POJ3009——Curling 2.0(DFS)
Curling 2.0 DescriptionOn Planet MM-21, after their Olympic games this year, curling is getting popu ...
随机推荐
-
eclipse生成uml
安装eclipse插件在help->Install new software里面add 有本地和网络两种 1.ModelGoon 该插件需要在file中new ModelGoon Diagram ...
-
20145129 《Java程序设计》第3周学习总结
20145129 <Java程序设计>第3周学习总结 教材学习内容总结 类与对象 定义类 一个原始码中可以有多个类定义,但只有一个是公开类(public),并且文档中的主文档名必须和公开类 ...
-
C++里消除Wunused
编译程序时,有一大堆警告总是不爽的.别人的代码也就忍了,不好去改.自己的可没法忍.看看C++里怎么消除Wunused警告. 先来看下面的程序: #include <iostream> in ...
-
Lombok : 让你写 Java代码像C#一样爽
前言 我曾经是一名 .Net 开发,如今的我是一名 Java 开发者.在我享受着 Java 成熟的生态时,我常常怀念 c# 简洁的语法:自动属性.类型推断.自动初始化器 .... 鱼,我所欲也,熊掌亦 ...
-
Linux(4)系统管理
系统管理 cal :查看当前月份和日历, 加-y查看整年日历 date :显示或设置时间 设置时间格式(需要管理员权限) date [MMDDhhmm[[CC]YY][.ss]]+format CC为 ...
-
lesson - 15 Linux系统日常管理4
内容概要:1. rsync 命令格式rsync [OPTION]... SRC DESTrsync [OPTION]... SRC [USER@]HOST:DESTrsync [OPTION].. ...
-
[bzoj4552][Tjoi2016&;Heoi2016]排序-二分+线段树
Brief Description DZY有一个数列a[1..n],它是1∼n这n个正整数的一个排列. 现在他想支持两种操作: 0, l, r: 将a[l..r]原地升序排序. 1, l, r: 将a ...
-
[HNOI2006]超级英雄
题目描述 现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金.主持人问题准备了若干道题目,只有当选手正确回答一道题后,才 ...
-
关于new Date()的日期格式处理
new Date()基本方法: var myDate = new Date(); myDate.getYear(); //获取当前年份(2位) myDate.getFullYear(); //获取完整 ...
-
mac下 将python2.7改为python3
1.查看当前电脑python版本 python -V // 显示2.7.x 2.用brew升级python brew update python 3.如果安装成功,去系统目录下回看到两个版本的pyth ...