讨论 / 《流星雨》记忆化宽搜WA70?
飞雪天涯 2010-09-23 01:53:00
点我顶贴 收藏 删除
查看状态 Show Status

状态题目:流星雨

题目编号:335-流星雨 查看该题

状态: Unaccepted

测评机: Xeost[5]

得分: 70分

提交日期: 2009-10-25 22:56:00

有效耗时: 1406毫秒

测试结果1: 通过本测试点|有效耗时219ms

测试结果2: 通过本测试点|有效耗时78ms

测试结果3: 测试结果错误.错误结果为:-1

正确结果应为:171

测试结果4: 测试结果错误.错误结果为:-1

正确结果应为:298

测试结果5: 测试结果错误.错误结果为:-1

正确结果应为:459

测试结果6: 通过本测试点|有效耗时219ms

测试结果7: 通过本测试点|有效耗时203ms

测试结果8: 通过本测试点|有效耗时234ms

测试结果9: 通过本测试点|有效耗时219ms

测试结果10: 通过本测试点|有效耗时234ms

提交代码: /*

查看题目 Show Problem

题目:流星雨

问题编号:335 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]

My Flag:Unaccepted

题目类型

搜索

描述

Bessie听说有一场壮丽的流星雨即将来临,而且据说陨石将要落下来撞击地球并摧毁一切它遇到的东西。为了保证自己的安全,bessie决定到一个安全的(永远不会被陨石击毁)地方去。

报道表明将有M颗陨石落下(1 ≤ M ≤ 50,000),第i个陨石将在Ti(0 ≤ Ti ≤ 1,000)时刻砸中(Xi,Yi)点(0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) 。每颗陨石将击毁它直接砸中的点以及四个与其直接相邻的点

她现在所处的地方是坐标系的原点,并从零时刻起出发,前往一个安全的地点,要求是她经过某点时该点未被击毁。她只能在坐标系的第一象限以及x,y轴的正半轴上活动。

求她能到达一个安全地点的最短时间。

输入格式

第一行:陨石个数M

第二行至第M+1行:第i+1行有三个整数表示:Xi,Yi,和Ti

数据范围见题目描述

输出格式

输出只有一行,即bessie所需的最短时间。如果她永远无法到达一个安全的地方,输出-1

样例输入

4

0 0 2

2 1 2

1 1 2

0 3 5

样例输出

5

*/

#include<iostream>

#define MAXN 1001

using namespace std;

struct rec{

int x;

int y;

rec(){}

rec(int _x,int _y):x(_x),y(_y){}

} Queue[MAXN*MAXN];

int qH,qT;

bool inQueue[MAXN][MAXN];

int T[MAXN][MAXN];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int dp[MAXN][MAXN];

bool cor(int x,int y){

return x>=0&&y>=0;

}

void attack(int x,int y,int t){

if (T[x][y]>=0) T[x][y]=min(T[x][y],t);

else T[x][y]=t;

if (cor(x-1,y)){

if (T[x-1][y]>=0) T[x-1][y]=min(T[x-1][y],t);

else T[x-1][y]=t;

}

if (cor(x,y-1)){

if (T[x][y-1]>=0) T[x][y-1]=min(T[x][y-1],t);

else T[x][y-1]=t;

}

if (cor(x+1,y)){

if (T[x+1][y]>=0) T[x+1][y]=min(T[x+1][y],t);

else T[x+1][y]=t;

}

if (cor(x,y+1)){

if (T[x][y+1]>=0) T[x][y+1]=min(T[x][y+1],t);

else T[x][y+1]=t;

}

}

int main (void){

int m,x,y,t;

cin>>m;

memset(T,-1,sizeof(T));

memset(dp,-1,sizeof(dp));

for (int i=0;i<m;++i){

cin>>x>>y>>t;

attack(x,y,t);

}

if (T[0][0]==0){

cout<<"-1";

return 0;

}

dp[0][0]=0;

inQueue[0][0]=true;

Queue[qH=0]=rec(0,0);

qT=1;

int ans=-1;

while (qH!=qT){

rec x=Queue[qH++];

qH%=MAXN*MAXN;

inQueue[x.x][x.y]=false;

if (T[x.x][x.y]==-1){

if (ans==-1) ans=dp[x.x][x.y];

ans=min(ans,dp[x.x][x.y]);

}

for (int i=0;i<4;++i){

int tx=x.x+dir[i][0],ty=x.y+dir[i][1];

if (!cor(tx,ty)) continue;

if (T[tx][ty]!=-1&&dp[x.x][x.y]+1>=T[tx][ty]) continue;

if (dp[tx][ty]!=-1&&dp[tx][ty]<=dp[x.x][x.y]+1) continue;

dp[tx][ty]=dp[x.x][x.y]+1;

if (inQueue[tx][ty]) continue;

Queue[qT++]=rec(tx,ty);

qT%=MAXN*MAXN;

inQueue[tx][ty]=true;

}

}

cout<<ans;

return 0;

}

#1 飞雪天涯@2009-10-25 07:57:00
回复 删除
3,4,5三个点总是过不去!
#2 webeskycn@2009-10-25 16:22:00
回复 删除
普通宽搜就ok.... - -!
#3 飞雪天涯@2009-10-28 05:08:00
回复 删除
还真是

查看状态 Show Status

状态题目:流星雨

题目编号:335-流星雨 查看该题

状态: Accepted

测评机: Xeost[5]

得分: 100分

提交日期: 2009-10-28 20:07:00

有效耗时: 1765毫秒

测试结果1: 通过本测试点|有效耗时62ms

测试结果2: 通过本测试点|有效耗时62ms

测试结果3: 通过本测试点|有效耗时422ms

测试结果4: 通过本测试点|有效耗时219ms

测试结果5: 通过本测试点|有效耗时688ms

测试结果6: 通过本测试点|有效耗时62ms

测试结果7: 通过本测试点|有效耗时62ms

测试结果8: 通过本测试点|有效耗时63ms

测试结果9: 通过本测试点|有效耗时62ms

测试结果10: 通过本测试点|有效耗时63ms

提交代码: /*

查看题目 Show Problem

题目:流星雨

问题编号:335 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]

My Flag:Unaccepted

题目类型

搜索

描述

Bessie听说有一场壮丽的流星雨即将来临,而且据说陨石将要落下来撞击地球并摧毁一切它遇到的东西。

为了保证自己的安全,bessie决定到一个安全的(永远不会被陨石击毁)地方去。

报道表明将有M颗陨石落下(1 ≤ M ≤ 50,000),第i个陨石将在Ti(0 ≤ Ti ≤ 1,000)时刻砸中(Xi,Yi)点(0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) 。

每颗陨石将击毁它直接砸中的点以及四个与其直接相邻的点

她现在所处的地方是坐标系的原点,并从零时刻起出发,前往一个安全的地点,要求是她经过某点时该点未被击毁。

她只能在坐标系的第一象限以及x,y轴的正半轴上活动。

求她能到达一个安全地点的最短时间。

输入格式

第一行:陨石个数M

第二行至第M+1行:

第i+1行有三个整数表示:Xi,Yi,和Ti

数据范围见题目描述

输出格式

输出只有一行,即bessie所需的最短时间。

如果她永远无法到达一个安全的地方,输出-1

样例输入

4

0 0 2

2 1 2

1 1 2

0 3 5

样例输出

5

*/

#include<iostream>

#include<queue>

#define MAXN 1001

using namespace std;

struct rec{

int x,y;

int step;

rec(int _x,int _y,int _step):x(_x),y(_y),step(_step){}

};

queue<rec> Queue;

int T[MAXN][MAXN];

bool visited[MAXN][MAXN];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

bool cor(int x,int y){

return x>=0&&y>=0;

}

void attack(int x,int y,int t){

if (T[x][y]>=0) T[x][y]=min(T[x][y],t);

else T[x][y]=t;

if (cor(x-1,y)){

if (T[x-1][y]>=0) T[x-1][y]=min(T[x-1][y],t);

else T[x-1][y]=t;

}

if (cor(x,y-1)){

if (T[x][y-1]>=0) T[x][y-1]=min(T[x][y-1],t);

else T[x][y-1]=t;

}

if (cor(x+1,y)){

if (T[x+1][y]>=0) T[x+1][y]=min(T[x+1][y],t);

else T[x+1][y]=t;

}

if (cor(x,y+1)){

if (T[x][y+1]>=0) T[x][y+1]=min(T[x][y+1],t);

else T[x][y+1]=t;

}

}

int main (void){

int m,x,y,t;

cin>>m;

memset(T,-1,sizeof(T));

for (int i=0;i<m;++i){

cin>>x>>y>>t;

attack(x,y,t);

}

if (T[0][0]==0){

cout<<"-1";

return 0;

}

Queue.push(rec(0,0,0));

visited[0][0]=true;

while (!Queue.empty()){

rec x=Queue.front();

Queue.pop();

// cout<<"expand...("<<x.x<<" "<<x.y<<")...expand"<<endl;

if (T[x.x][x.y]==-1){

cout<<x.step;

return 0;

}

for (int i=0;i<4;++i){

int tx=x.x+dir[i][0],ty=x.y+dir[i][1];

// cout<<"get point..."<<tx<<" "<<ty<<endl;

if (!cor(tx,ty)) continue;

if (visited[tx][ty]) continue;

if (T[tx][ty]!=-1&&T[tx][ty]<=x.step+1) continue;

// cout<<"examined"<<endl;

visited[tx][ty]=true;

Queue.push(rec(tx,ty,x.step+1));

}

}

cout<<"-1";

return 0;

}

#4 烂笔头@2010-09-23 01:53:00
回复 删除
能不能讲下原理
查看更多回复
提交回复