状态题目:流星雨
题目编号: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;
}
查看状态 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;
}