| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
110120_119#include<cstdio>
#pragma warning (disable:4996)
using namespace std;
int col, row;
int minStep; //最小步数
int field[110][110]; //存储地图
int direction[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; //方向
void dfs(int x, int y, int step)
{
if (step > 10 || step > minStep)
return;
for (int i = 0; i < 4; i++)
{
int nx = x + direction[i][0]; //先选择一个方向让石头飞
int ny = y + direction[i][1];
//printf("xyi: %d %d %d\n", x, y, i);
while (0 <= nx && nx < row && 0 <= ny && ny < col) //只要没有越界就让石头一直飞
{
//对飞行过程中可能出现的情况做判断
switch (field[nx][ny])
{
case 0: //空地情况
nx += direction[i][0]; //朝当前的方向继续飞
ny += direction[i][1];
break;
case 3: //到达终点
if (step + 1 < minStep) //若当前步数小于最小步数,则更新步数
minStep = step + 1;
return;
case 1: //遇到了石头,分为两种情况,一是:相邻石头(不可以撞碎),二是:飞行过程中遇到石头,则撞碎
if (!(nx - direction[i][0] == x && ny - direction[i][1] == y)) //若后退一步不是初始位置,说明不是相邻石头
{
field[nx][ny] = 0; //不是相邻石头则将其变成空地
dfs(nx - direction[i][0], ny - direction[i][1], step + 1); //后退一步,再次深搜,步数加1
field[nx][ny] = 1; //刚才的石头需要复原,供下一次尝试
}
nx = -1; //不论是否是相邻石头,只要碰到石头,则需要换方向,此时需要破坏掉while中的条件,使while循环终止,继续进行for循环
break;
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int sx, sy;
while (scanf("%d %d", &col, &row) != EOF)
{
if (col == 0 && row == 0)
return 0;
minStep = 11;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
scanf("%d", &field[i][j]);
if (field[i][j] == 2) //记录开始位置
{
sx = i;
sy = j;
field[i][j] = 0; //将开始的点变为空地
}
}
}
dfs(sx, sy, 0);
if (minStep > 10)
minStep = -1; //步数大于10步则说明不可以到达终点
printf("%d\n", minStep); //打印最小步数
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator