OpenJ_Bailian——4115鸣人和佐助(带状态的A*)
2024-08-30 13:58:01
Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?
Input
输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。
Output
输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。
Sample Input
样例输入1
4 4 1
#@##
**##
###+
****
样例输入2
4 4 2
#@##
**##
###+
****
Sample Output
样例输出1
6
样例输出2
4
跟上一题一个意思……状态差不多……神奇的是这题居然没人做……A*比普通BFS慢……估计是数据太小和我估价函数选的搓的缘故。1A水
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x,y) memset(x,y,sizeof(x))
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=205;
struct info
{
int x;
int y;
int zkl;
int step;
int h;
bool operator<(const info &b)const
{
if(step+h!=b.step+b.h)
return step+h>b.step+b.h;
if(step!=b.step)
return step>b.step;
if(zkl!=b.zkl)
return zkl>b.zkl;
}
};
info S,T,direct[4]={{0,1,1,0},{0,-1,1,0},{1,0,1,0},{-1,0,1,0}};
inline info operator+(const info &a,const info &b)
{
info c;
c.x=a.x+b.x;
c.y=a.y+b.y;
c.step=a.step+b.step;
return c;
}
inline bool operator==(const info &a,const info &b)
{
return (a.x==b.x&&a.y==b.y);
}
int n,m,t;
char pos[N][N];
int vis[N][N][10];
priority_queue<info>Q;
void init()
{
MM(pos,0);
MM(vis,0);
while (!Q.empty())
Q.pop();
}
bool check(const info &a)
{
return (a.x>=0&&a.x<m&&a.y>=0&&a.y<n&&a.zkl<=t&&!vis[a.x][a.y][a.zkl]);
}
inline int ABS(const int &n)
{
return n<0?-n:n;
}
int main(void)
{
int i,j,r;
while (~scanf("%d%d%d",&m,&n,&t))
{
r=-1;
init();
for (i=0; i<m; i++)
{
scanf("%s",pos[i]);
for (j=0; j<n; j++)
{
if(pos[i][j]=='@')
{
S.x=i;
S.y=j;
S.step=0;
S.zkl=0;
}
else if(pos[i][j]=='+')
{
T.x=i;
T.y=j;
}
}
}
S.h=S.step+ABS(S.x-T.x)+ABS(S.y-T.y);
Q.push(S);
vis[S.x][S.y][S.zkl]=1;
while (!Q.empty())
{
info now=Q.top();
Q.pop();
if(now==T)
{
r=now.step;
break;
}
for (i=0; i<4; i++)
{
info v=now+direct[i];
v.zkl=now.zkl+(pos[v.x][v.y]=='#');
if(check(v))
{
v.step=now.step+1;
v.h=v.step+ABS(v.x-T.x)+ABS(v.y-T.y);
Q.push(v);
vis[v.x][v.y][v.zkl]=1;
}
}
}
printf("%d\n",r);
}
return 0;
}
最新文章
- 【转】字符集和字符编码(Charset &; Encoding)
- Google的Bigtable学习笔记(不保证正确性)
- SPOJ VLATTICE Visible Lattice Points 莫比乌斯反演
- bss段为什么需要初始化?
- xml基础小结
- 【转】Ubuntu 修改hosts
- 网易云课堂_C++开发入门到精通_章节4:运算符重载
- java_eclipse_svn 与服务器同步时 ,忽略某类型文件和文件夹
- 基于appium的移动端自动化测试,密码键盘无法识别问题
- Java中实现十进制数转换为二进制的三种思路
- 易忽视的Python知识点
- win10同时安装 office2016和visio2016
- Achievements
- 深度优先搜素之N皇后问题
- Jmeter(三十四)_Beanshell解析并提取json响应
- 第三个Sprint冲刺第九天(燃尽图)
- bzoj 4318 OSU! - 动态规划 - 概率与期望
- C# 自动升级
- C# 泛型的简单讲解和应用
- JBPM4.4_执行流程实例