POJ 3009 ( Curling 2.0 ）
标签：alt ide 上下左右 none turn 超过 int clu 消失
题目链接：http://poj.org/problem?id=3009
题意： （1） 一个球只能沿着上下左右方向移动，且只能走直线，沿着一个方向一直走下去；
（2）若碰到障碍物冰块就会停止，停止位置是在障碍物之前的位置，并且停止位置的下一位置的障碍物消失,这种情况算滚动1次；
（3）游戏结束的情况是：滚动次数超过10次，或者球滚出界了，游戏结束并且输出 - 1；
思路： 这道题一看感觉无从下手，和迷宫类的搜索不一样，搜索不是一步一步的，而是整条直线的搜，但是正是滚动次数不超过10，所以可以采用暴力枚举；
ac代码：（由于自己写的代码实在不美观就copy了一个美观的代码 0.0 ）
#include
#include
#include string.h>
#include string>
#include
#include #define judge(x,y) x>=1&&x=1&&yusing namespace std;
int n,m,sx,sy,ex,ey; //设置全局变量
int map[25][25];
//设置方向数组优化深搜代码
int xx[]={-1,1,0,0};
int yy[]={0,0,-1,1};
int step,steps;
void dfs(int x,int y)
{
if(step>10)return; // 递归出口，步数大于10步就返回
for(int i=0;i4;i++)
{
int dx=x+xx[i];
int dy=y+yy[i];
int ok=0; //作为某个方向能不能走的一个标志变量
while(judge(dx,dy))
{
ok=1;
if(dx==ex&&dy==ey)
{
if(stepstep;
}
dx+=xx[i]; //搜索整条直线
dy+=yy[i];
}
if(map[dx][dy]==1&&ok)
{
step++;
map[dx][dy]=0;
dfs(dx-xx[i],dy-yy[i]);
step--;
map[dx][dy]=1;
}
}
}
int main()
{
while(cin>>m>>n)
{
if(n==0&&m==0)break;
memset(map,0,sizeof(map));
for(int i=1;i)
for(int j=1;j)
{
cin>>map[i][j];
if(map[i][j]==2){sx=i;sy=j;}
if(map[i][j]==3){ex=i;ey=j;}
}
step=1;
steps=1000000;
dfs(sx,sy);
if(steps>10) cout1endl;
else coutendl;
}
return 0;
}
View Code
18:25:02
POJ 3009 ( Curling 2.0 ）
标签：alt ide 上下左右 none turn 超过 int clu 消失
原文地址：https://www.cnblogs.com/jaszzz/p/12547517.html
评论