13 条题解
-
1
Mario_sz LV 7 @ 2016-10-30 16:02:29
这道冰原探险就是个BFS，刚开始做的时候没有考虑到冰川是4面（好像有点傻。。），然后判断只要到过这个冰川就不能在到达了，，结果只得了60分（能得这么多已经很开心了。），，后来一想，应该是**冰川的一侧不能到达两遍！！**于是改了改就A了。
代码如下：
/*
My convictions will not falter.--Poppy
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 50000
using namespace std;
int tail=0,head=0,u,n,b1,b2,e1,e2;
int qx[N],qy[N],qd[N],qt[N],lx[N],ly[N],rx[N],ry[N],pd[N][5];
/*qx,qy,qd,qt都是队列，qd是当前的小冰块滑动的方向（1代表下面有冰川将要左右滑，-1反之），
qx,qy就是坐标啦，qt是到达当前状态所需的步数，pd就是判断当前状态是否已经到达过，
每一个冰川四种状态*/
int judge(int x,int y,int d)
{
int m1=2147483647,mi1=-1,m2=-2147483647,mi2=-1,i;
if(d==1)//左右滑
{
for(i=1;i<=n;i++)
{
if(ly[i]<m1&&ly[i]>y&&lx[i]<=x&&rx[i]>=x)//如果向右滑能碰到的冰川可以挡住冰块
m1=ly[i],mi1=i;
if(ry[i]>m2&&ry[i]<y&&lx[i]<=x&&rx[i]>=x)//向左
m2=ry[i],mi2=i;
}
if(e1==x&&e2<m1&&e2>m2) return 1;
if(mi1>0&&!pd[mi1][1])
qx[++head]=x,qy[head]=m1-1,qd[head]=-d,qt[head]=qt[u]+1,pd[mi1][1]=1;
//qd[head]=-d，这次左右滑能停下，下次必定上下滑，因为如果再左右滑，又回到了原来的状态，必定不是最优
if(mi2>0&&!pd[mi2][3])
qx[++head]=x,qy[head]=m2+1,qd[head]=-d,qt[head]=qt[u]+1,pd[mi2][3]=1;
}
if(d==-1)//上下滑
{
for(i=1;i<=n;i++)
{
if(lx[i]<m1&&lx[i]>x&&ly[i]<=y&&ry[i]>=y)//向下
m1=lx[i],mi1=i;
if(rx[i]>m2&&rx[i]<x&&ly[i]<=y&&ry[i]>=y)//向上
m2=rx[i],mi2=i;
}
if(e2==y&&e1<m1&&e1>m2) return 1;
if(mi1>0&&!pd[mi1][4])
qx[++head]=m1-1,qy[head]=y,qd[head]=-d,qt[head]=qt[u]+1,pd[mi1][4]=1;
if(mi2>0&&!pd[mi2][2])
qx[++head]=m2+1,qy[head]=y,qd[head]=-d,qt[head]=qt[u]+1,pd[mi2][2]=1;
}
return 0;
}
int main()
{
scanf("%d",&n);
scanf("%d%d",&b1,&b2);
scanf("%d%d",&e1,&e2);
int i;
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&lx[i],&ly[i],&rx[i],&ry[i]);
tail=0,head=0;
if(judge(b1,b2,1))
{
printf("%d",qt[u]+1);
return 0;
}
if(judge(b1,b2,-1))
{
printf("%d",qt[u]+1);
return 0;
}//一开始的冰块可以向4个方向滑
while(tail<head)
{
tail++;
u=tail;
if(judge(qx[u],qy[u],qd[u]))
{
printf("%d",qt[u]+1);
return 0;
}
}
printf("0");
return 0;
}
-
0
裸Bfs+Hashmap判重+上一次上下滑这一次只能左右滑剪枝
代码又臭又长
注意地图坐标可能为负#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> #include<map> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } struct Point { int x,y,time,last; } Start,End,LeftUp[5005],RightDown[5005]; map<int,map<int,int> >vst; int n; bool Judge(int x,int y,int direction,int& Nextx,int& Nexty) { if(direction==1) { //右滑 Nextx=0x7fffffff/2; for(int i=1; i<=n; i++) if(x<LeftUp[i].x-1&&y>=LeftUp[i].y&&y<=RightDown[i].y) { Nextx=min(Nextx,LeftUp[i].x-1); Nexty=y; } if(x<End.x&&y==End.y&&(Nextx>=End.x||!Nextx)) { Nextx=End.x; Nexty=End.y; return true; } if(Nextx!=0x7fffffff/2)return true; } else if(direction==2) { //左滑 Nextx=-0x7fffffff/2; for(int i=1; i<=n; i++) if(x>RightDown[i].x+1&&y>=LeftUp[i].y&&y<=RightDown[i].y) { Nextx=max(Nextx,RightDown[i].x+1); Nexty=y; } if(x>End.x&&y==End.y&&(Nextx<=End.x||!Nextx)) { Nextx=End.x; Nexty=End.y; return true; } if(Nextx!=-0x7fffffff/2)return true; } else if(direction==3) { //上滑 Nexty=-0x7fffffff/2; for(int i=1; i<=n; i++) if(y>RightDown[i].y+1&&x>=LeftUp[i].x&&x<=RightDown[i].x) { Nextx=x; Nexty=max(Nexty,RightDown[i].y+1); } if(x==End.x&&y>End.y&&(Nexty<=End.y||!Nexty)) { Nextx=End.x; Nexty=End.y; return true; } if(Nexty!=-0x7fffffff/2)return true; } else { //下滑 Nexty=0x7fffffff/2; for(int i=1; i<=n; i++) if(y<LeftUp[i].y-1&&x>=LeftUp[i].x&&x<=RightDown[i].x) { Nextx=x; Nexty=min(Nexty,LeftUp[i].y-1); } if(x==End.x&&y<End.y&&(Nexty>=End.y||!Nexty)) { Nextx=End.x; Nexty=End.y; return true; } if(Nexty!=0x7fffffff/2)return true; } return false; } void Bfs() { queue<Point>Q; Q.push(Start); vst[Start.x][Start.y]=1; while(!Q.empty()) { Point Now=Q.front(); Q.pop(); if(Now.x==End.x&&Now.y==End.y) { printf("%d\n",Now.time); return; } int Nextx=0,Nexty=0,i=1,Max=4; if(Now.last==1||Now.last==2)i=3; else if(Now.last==3||Now.last==4)Max=2; for(; i<=Max; i++) if(Judge(Now.x,Now.y,i,Nextx,Nexty)&&(!vst.count(Nextx)||!vst[Nextx].count(Nexty))) { Q.push((Point) { Nextx,Nexty,Now.time+1,i }); vst[Nextx][Nexty]=1; } } puts("0"); } int main() { n=Get_Int(); Start.x=Get_Int(),Start.y=Get_Int(); End.x=Get_Int(),End.y=Get_Int(); for(int i=1; i<=n; i++) { LeftUp[i].x=Get_Int(); LeftUp[i].y=Get_Int(); RightDown[i].x=Get_Int(); RightDown[i].y=Get_Int(); } Bfs(); return 0; } -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 322ms
├ 测试数据 10：答案正确... 228ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：591msFlag Accepted
题号 P1366
类型(?) 图结构
通过 30人
提交 100次
通过率 30%
难度 4just 宽搜
-
0
编译通过...
├ 测试数据 01：答案错误...程序输出比正确答案长
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：0 有效耗时：0ms
我撞棉花撞死算了 -
0
LV 0 @ 2008-07-21 09:24:21
古老的搜索题。。。放在现在没了空间复杂度。。当时要写很久很久+卡时的吖~~！
Mario_sz
LV 7
@ 2016-10-30 16:02:29
- 1
