【t052】冰岛
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
假设你在一个n*n的冰面上,并且你想到达这个冰面的某处,可是由于冰面太滑了,所以当你向某个方向出发后,你没有办法使自己
停下来直到你碰到了某个障碍物——因为你可以抓住障碍物使得你的身体停止运动。
因为你已经知道了整个地图,所以你决定在行动之前先计算出最快可到达目标的路线,使得你可以不用走太多冤枉路,这时你决定编
程解决这个问题……
【输入格式】
第一行包括一个正整数n(n<=1000)
以下n行,每行包括n个数字(0或1),0表示该点为空地可以滑行,1表示该点为障碍物(障碍物无法穿过)。保证最外圈的地形为障
碍物,也就是你无法离开这个地图。
接下来1行包括2个整数x,y(1<=x,y<=n),表示一开始你处于坐标(x,y)
再接下来1行包括2个整数x2,y2(1<=x2,y2<=n),表示你想要到达的目标为(x2,y2)
【输出格式】
只有一个整数t,表示能到达目标的最短时间(假设每经过一次滑行需要花费1单位的时间,无论这次滑行距离的长短)。所谓到达目
标要求必须停留在(x2,y2),也就是你不能在到达之后被迫滑向下一个点。当你无法到达目标点时,你只须输出一行字符串’
impossible’。
样例1说明:由(2,2)到(2,3),再由(2,3)到(4,3),2次滑行到达终点。
Sample Input
5
1 1 1 1 1
1 0 0 1 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
2 2
4 3
Sample Output
2
Sample Input2
4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
2 2
3 3
Sample Output2
impossible
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t052
【题解】
一开始判断一下起点和终点在不在障碍物上;如果其中之一在障碍物上就直接输出无解;
有可能起点和终点在同一个位置上;别搞笑了特判一下吧。
然后就4个方向搜一搜就好;
也不用判断边界;因为它保证了4个边界都有障碍;
用cin输入会GG..用更快的输入方式吧。
我好菜啊。一直在做水题;
【完整代码】
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void rel(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void rei(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
const int MAXN = 1300;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
struct abc
{
int x,y,step;
};
int n,a0,b0,a1,b1,h[MAXN][MAXN];
bool bo[MAXN][MAXN];
queue <abc> dl;
int main()
{
// freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
rep1(j,1,n)
rei(h[i][j]);
rei(a0);rei(b0);rei(a1);rei(b1);
if (h[a0][b0]||h[a1][b1])
puts("imposiible");
else
{
bool ok = false;
memset(bo,false,sizeof(bo));
bo[a0][b0] = true;
if (bo[a1][b1])
{
puts("0");
return 0;
}
abc tt;
tt.x = a0,tt.y = b0,tt.step = 0;
dl.push(tt);
while (!dl.empty())
{
int x = dl.front().x,y = dl.front().y,s = dl.front().step;
dl.pop();
rep1(i,1,4)
{
int tx = x,ty = y;
while (!h[tx+dx[i]][ty+dy[i]])
tx+=dx[i],ty+=dy[i];
if (bo[tx][ty])
continue;
bo[tx][ty] = true;
tt.x = tx;tt.y = ty;tt.step=s+1;
dl.push(tt);
if (tx==a1 && ty==b1)
{
ok = true;
cout << s+1<<endl;
break;
}
}
if (ok) break;
}
if (!ok)
puts("impossible");
}
return 0;
}
最新文章
- 分享一个快速测试ios软件的工具
- spring mvc定时任务的简单使用
- 转载:混淆包含SlidingMenu、gson等Android代码的proguard写法
- Java基础-String 存储机制管理
- 使用Redis来实现LBS的应用
- 关于线程池ThreadPoolExecutor使用总结
- jrae源码解析(一)
- 直接粘贴代码到网络上:command-line pastebins
- 块和内嵌总结,以及各个标签的应用。其中的ul ol dl特殊定义为auto,使得里面的内容展开
- HTTP严格安全传输(HTTP Strict Transport Security, HSTS)chromuim实现源码分析(一)
- Js 跳出两级循环的方法
- 2017《JAVA技术》预备作业2-计科1502-19-何俏依
- jenkins执行shell提示命令不存在
- redhat修改网卡名称
- Data Plane
- Oracle SQL部分练习题
- Python中浮点数精度处理
- Codeforces 916B - Jamie and Binary Sequence (changed after round)
- salt之pillar组件
- TextView显示HTML文本时<;IMG>;标签指定图片的显示处理
热门文章
- 2017国家集训队作业[agc006f]Blackout
- [AngularFire] Resolve snapshotChanges doesn&#39;t emit value when data is empty
- Fedora 10下应用网络模拟器NS心得
- HttpUtility.UrlEncode,Server.UrlEncode 的区别
- 随手记录---transform 属性
- python学习三:列表,元组
- [置顶]
 MVC三层架构在各框架中的特征
- JSP页面开发规范案例
- HDU 3131 One…Two…Five! (暴力搜索)
- 3lession-python编程规范