ZOJ 3890 Wumpus
Wumpus
Time Limit: 2 Seconds
Memory Limit: 65536 KB
One day Leon finds a very classic game called Wumpus.The game is as follow.
Once an agent fell into a cave. The legend said that in this cave lived a kind of monster called Wumpus, and there were horrible pits which could lead to death everywhere. However, there were also a huge amount of gold in the cave. The agent must be careful
and sensitive so that he could grab all of the gold and climb out of the cave safely.
The cave can be regarded as a n*n board. In each square there could be a Wumpus, a pit, a brick of gold, or nothing. The agent would be at position (0,0) at first and headed right.(As the picture below)
name=Wumpus1.png">
For each step, there are six possible movements including going forward, turning left, turning right, shooting, grabbing the gold, and climbing out of the cave. If the agent steps into a square containing a pit or Wumpus, he will die. When the agent shoots,
the Wumpus in front of him will die. The goal of the agent is to grab all of the gold and return to the starting position and climb out(it's OK if any Wumpus is still living).When a brick of gold is grabbed successfully, you will gain 1000 points. For each
step you take, you will lose 10 points.
Your job is to help him compute the highest point he can possibly get.
For the purpose of simplification, we suppose that there is only one brick of gold and the agent cannot shoot the Wumpus.
If there is a pit at (0, 0), the agent dies immediately. There will not be a Wumpus at (0, 0).
Input
There are multiple cases. The first line will contain one integer k that indicates the number of cases.
For each case:
The first line will contain one integer n (n <= 20).
The following lines will contain three integers, each line shows a position of an object. The first one indicates the type of the object. 1 for Wumpus, 2 for pit and 3 for gold. Then the next two integers show the x and y coordinates of the object.
The input end with -1 -1 -1. (It is guaranteed that no two things appear in one position.)
Output
The output contains one line with one integer, which is the highest point Leon could possibly get. If he cannot finish the game with a non-negative score, print "-1".
Sample Input
2
3
1 1 1
2 2 0
3 2 2
-1 -1 -1
3
1 1 1
3 2 2
-1 -1 -1
Sample Output
850
870
Hint
For the sample 1, the following steps are taken:
turn left, forward, forward, turn right, forward, forward, grab, turn left, turn left, forward, forward, turn left, forward, forward, climb.
There are in all 15 steps, so the final score is 840. For the sample 2 , the path is as follow:
Author: JIANG, Kairong
Source: ZOJ Monthly, July 2022
转弯bfs。用四维标记
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
int n;
struct node
{
int x,y,gg,cost,fangxiang;
};
int vis[22][22][4][2];//一维,二维坐标。三维四个方向 四维金子拿了没有
int dir[4][2]= //zai 0 0
{
1,0, // 開始向右,1,0。
0,-1,
-1,0,
0,1,
};
char mp[22][22];
int judge(node &now)
{
if(now.x<0 ||now.y<0 ||now.x>=n ||now.y>=n)
return 0;
if(mp[now.x][now.y]==1)
return 0;
if(vis[now.x][now.y][now.fangxiang][now.gg])
return 0;
vis[now.x][now.y][now.fangxiang][now.gg]=1;
if(mp[now.x][now.y]==3 &&now.gg==0)
{
now.cost+=1000;
now.cost-=10;
now.gg=1;
}
return 1;
}
int bfs()
{
memset(vis,0,sizeof(vis));
queue<node>q;
node st,ed,now;
st.fangxiang=st.cost=st.gg=st.x=st.y=0;
q.push(st);
int ans=0;
while(!q.empty())
{
ed=q.front();
if(ed.x==0 &&ed.y==0)
ans=max(ans,ed.cost);
q.pop();
for(int i=-1; i<=1; i++)
{
now=ed;
now.cost-=10;
if(i==0)
{
now.x+=dir[now.fangxiang][0];
now.y+=dir[now.fangxiang][1];
}
else
now.fangxiang=(now.fangxiang+i+4)%4;
if(judge(now))
q.push(now);
}
}
return ans-10;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b,p;
int flag=0;
scanf("%d",&n);
memset(mp,0,sizeof(mp));
while(scanf("%d%d%d",&a,&b,&p)!=EOF&&a!=-1 &&b!=-1&&p!=-1)
{
if(a==1)
mp[b][p]=1;
else if(a==2)
{
mp[b][p]=1;
if(b==0 &&p==0)
flag=1;
}
else if(a==3)
mp[b][p]=3;
}
int ans1=bfs();
if(flag)
{
cout<<-1<<endl;
continue;
}
if(ans1<0)
cout<<-1<<endl;
else
cout<<ans1<<endl;
}
return 0;
}
最新文章
- HTTP 错误 404.3 - Not Found 由于扩展配置问题而无法提供您请求的页面。如果该页面是脚本 ,请添加处理程序。如果下载文件,请添加 MIME 映射。 IIS站点中添加WCF项目后浏览网站报错解决方法。
- 学习笔记之-------UIScrollView 基本用法 代理使用
- Linux high memory 学习总结
- 6.3 Android Framework
- ARM-Linux S5PV210 UART驱动(6)----platform device的添加
- 状态机的c语言编程
- vs.net 2013 Saffolding功能扩展
- Win7下Redmine2.0.3+Mysql55+Ruby1.8.7成功安装记录分享
- 学会Func
- make执行过程
- zepto全选按钮之全选会根据按钮是否被全部选中更改状态
- spring AOP原理
- 201521123086《JAVA程序设计》第五周作业
- OS X 平台的 8 个实用终端工具
- Spring Boot(六):如何优雅的使用 Mybatis
- webform的代码设计文件莫名出错的解决
- HTML+CSS技术实现网页滑动门效果
- [shell] 脚本使用 【记录】
- [Ting&#39;s笔记Day4]将Ruby on Rails项目部署到Heroku
- 2017/05/02 java 基础 随笔