题目
宝葫芦被放在一个城堡里。城堡由n*m个方格组成，你只能从当前所在的方格跳到相邻的4个方格里，而且不能跳出城堡的范围。城堡中某些方格里有弹簧，每个弹簧具有一个特定能量p，不同弹簧的p值不一定相同。如果你跳到一个有弹簧的方格，就会立刻沿着原来运动的方向继续跳p格，如果跳到的方格里又有弹簧，就马上继续跳，直到跳到一个空的方格或者被墙挡住无法继续前进为止。你能否尽快找到宝葫芦吗？
输入：有多组数据。在每组数据中，{dy}行有两个整数，n和m(3=<n,m<=100)，分别是城堡的行数和列数。其后是一个非负整数k，表示弹簧的个数。在接下来的k行里，每行有三个正数x, y, p，以空格隔开，其中x和y是弹簧的坐标(2=<x<=n-1, 2=<y<=m-1)，p是弹簧的能量。在下面的两行里，分别是你和宝葫芦的坐标。此外，你在空中经过的弹簧对你没有任何影响。已知你、宝葫芦和弹簧的初始位置都不同。x坐标轴的范围是1到n，y坐标轴的范围是1到m。
输出：
最少的步数，或者impossible
输入示例：
10 10
2
2 7 5
2 3 3
2 8
1 1
输出示例：
3
解题思路
|
|
|
|
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
struct s
{
int x;
int y;
int step;
};
struct s a[10010];
int b[105][105];
int c[105][105];
void main()
{
int m,n;
int t;
int i,j;
int temp1,temp2,temp3;
int begin,end;
while(scanf("%d %d",&n,&m)!=EOF)
{
scanf("%d",&t);
for(i=0;i<105;i++)
for(j=0;j<105;j++)
{
b[i][j]=0;
c[i][j]=0;
}
for(i=0;i<t;i++)
{
scanf("%d %d %d",&temp1,&temp2,&temp3);
b[temp1][temp2]=temp3;//设定弹簧位置和能量
}
scanf("%d %d",&temp1,&temp2);
a[0].x=temp1;a[0].y=temp2;a[0].step=0;
c[temp1][temp2]=1;
scanf("%d %d",&temp1,&temp2);//结束输入
if(b[temp1][temp2]>0)//如果放宝葫芦的地方已经放了弹簧
goto ABC;
else
b[temp1][temp2]=-1;//设定宝葫芦的位置
begin=0;end=1; //设定标志位
while(begin<end)
{
if(b[a[begin].x][a[begin].y]==-1)//判断是否是宝葫芦
break;
else
{
a[end].x=a[begin].x-1;//to upper
a[end].y=a[begin].y;
while(b[a[end].x][a[end].y]>0)
{
temp1=b[a[end].x][a[end].y];
a[end].x=a[end].x-temp1;
if(a[end].x<1)
{
a[end].x=1;
break;
}
}
if(a[end].x<1)
a[end].x=1;
if(c[a[end].x][a[end].y]==1)//判断该点是否走过
end--;
else
{
a[end].step=a[begin].step+1;
c[a[end].x][a[end].y]=1;
}
end++;
a[end].x=a[begin].x+1;//to down
a[end].y=a[begin].y;
while(b[a[end].x][a[end].y]>0)
{
temp1=b[a[end].x][a[end].y];
a[end].x=a[end].x+temp1;
if(a[end].x>n)
{
a[end].x=n;
break;
}
}
if(a[end].x>n)
a[end].x=n;
if(c[a[end].x][a[end].y]==1)
end--;
else
{
a[end].step=a[begin].step+1;
c[a[end].x][a[end].y]=1;
}
end++;
a[end].x=a[begin].x;//to left
a[end].y=a[begin].y-1;
while(b[a[end].x][a[end].y]>0)
{
temp1=b[a[end].x][a[end].y];
a[end].y=a[end].y-temp1;
if(a[end].y<1)
{
a[end].y=1;
break;
}
}
if(a[end].y<1)
a[end].y=1;
if(c[a[end].x][a[end].y]==1)
end--;
else
{
a[end].step=a[begin].step+1;
c[a[end].x][a[end].y]=1;
}
end++;
a[end].x=a[begin].x;//to right
a[end].y=a[begin].y+1;
while(b[a[end].x][a[end].y]>0)
{
temp1=b[a[end].x][a[end].y];
a[end].y=a[end].y+temp1;
if(a[end].y>m)
{
a[end].y=m;
break;
}
}
if(a[end].y>m)
a[end].y=m;
if(c[a[end].x][a[end].y]==1)
end--;
else
{
a[end].step=a[begin].step+1;
c[a[end].x][a[end].y]=1;
}
end++;
}
begin++;
}
if(begin<end)
printf("%d\n",a[begin].step);
else
ABC : printf("impossible\n");
}
}
|
|
