Problem D: XYZZY
ADVENT: /ad�vent/, n.
The prototypical computer adventure game, first designed by Will Crowther on the PDP-10 in the mid-1970s as an attempt at computer-refereed fantasy gaming, and expanded into a puzzle-oriented game by Don Woods
at Stanford in 1976. (Woods had been one of the authors of INTERCAL.) Now better known as Adventure or Colossal Cave Adventure, but the TOPS-10 operating system permitted only six-letter filenames in uppercase. See also vadding, Zork, and Infocom.
It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developedAdvent-style games for deployment on the Y-Crate. Your job
is to test a number of these designs to see which are winnable.
Each game consists of a set of up to 100 rooms. One of the rooms is thestartand one of the rooms is thefinish. Each room has anenergy valuebetween -100 and +100. One-way doorways interconnect
pairs of rooms.
The player begins in the start room with 100energy points. She may pass through any doorway that connects the room she is in to another room, thus entering the other room. The energy value of this room
is added to the player's energy. This process continues until she wins by entering the finish room or dies by running out of energy (or quits in frustration). During her adventure the player may enter the same room several times, receiving its energy each
time.
The input consists of several test cases. Each test case begins withn, the number of rooms. The rooms are numbered from 1 (the start room) ton(the finish room). Input for thenrooms
follows. The input for each room consists of one or more lines containing:
- the energy value for roomi
- the number of doorways leaving roomi
- a list of the rooms that are reachable by the doorways leaving roomi
The start and finish rooms will always have enery level 0.A line containing -1 follows the last test case.
In one line for each case, output "winnable" if it is possible for the player to win, otherwise output "hopeless".
Sample Input
5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0
5
0 1 2
20 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
21 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
20 2 1 3
-60 1 4
-60 1 5
0 0
-1
Output for Sample Input
hopeless
hopeless
winnable
winnable
G. V. Cormack
这道题用到了一个独特的算法SPFA,同时需要判断是否存在正环,刚开始的无从下手,后来参考别人的代码,就看明白了。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 110
int grid[maxn][maxn],val[maxn][maxn],num[maxn][maxn];
int vis[maxn],dis[maxn];
int n,tag,s;
queue<int> t;
void dfs(int pos)
{
if(pos==n)
{
tag=1;
return;
}
vis[pos]=1;
for(int i=1;i<=n;i++)
{
if(grid[pos][i]&&vis[i]==0&&tag==0)
{
dfs(i);
}
}
}
void spfa()
{
while(!t.empty())
t.pop();
memset(vis,0,sizeof(vis));
//memset(dis,0,sizeof(dis));
vis[1]=1,dis[1]=100;
s=0;
t.push(1);
while(!t.empty())
{
int x=t.front();
t.pop();
vis[x]=0;
for(int i=1;i<=n;i++)
{
if(grid[x][i])
{
if(dis[i]<dis[x]+val[x][i])
{
num[x][i]++;
dis[i]=dis[x]+val[x][i];
if(num[x][i]>=n)//判断回路
{
s=i;
return;
}
if(vis[i]==0&&dis[i]>0)
{
t.push(i);
vis[i]=1;
}
}
}
}
}
}
int main()
{
while(cin>>n&&n!=-1)
{
memset(val,0,sizeof(val));
memset(grid,0,sizeof(grid));
memset(num,0,sizeof(num));
//memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
int i,j,k,v,l,r;
for(i=1;i<=n;i++)
{
cin>>v>>k;
for(j=1;j<=k;j++)
{
cin>>r;
grid[i][r]=1;
val[i][r]=v;
}
}
spfa();
if(!s)
{
tag=1;
if(dis[n]<=0)
tag=0;
}
else
{
tag=0;
memset(vis,0,sizeof(vis));
dfs(s);//判断从回路中某点出发能否到达终点
}
if(tag) cout<<"winnable"<<endl;
else cout<<"hopeless"<<endl;
}
return 0;
}
分享到:
相关推荐
ANSI Common Lisp 中但不在 xyzzy 中的一系列计划好的东西。 安装 从网络安装程序 。 如何使用 我会暂时阅读它。 (eval-when (:execute :compile-toplevel :load-toplevel) (require "ansify")) ansify 实现的...
木乃伊类似于拉链的结构: 以易于检索的形式存储从根到所选节点的路径具有统一的内部树结构(每个分支节点中的:children矢量)基本原理我在...用法添加到您的project.clj : [mkremins/xyzzy " 0.3.4 " ]执照。 乱走。
先决条件 节点 npm 口(> = 3.9.0) 安装 npm install 用法 gulp watch serve 转到 特征 ES6(+棉绒) SCSS HTTP服务器 LiveReload
xyzzy.github.io:我的个人博客的Jekyll来源
假装您的度量处理器是Xyzzy。 从Apache Kafka(0.10.1.0或更高版本)中获取度量标准信息,并将其保存到PostgreSQL(9.5或更高版本;使用INSERT ... ON CONFLICT DO NOTHING)。 删除使用者偏移量后可以安全地重新...
缓冲区列表(缓冲区菜单),例如Emacs或xyzzy,可以保存/关闭文档。 特征 显示开幕文件清单 保存和/或关闭标记的文档 配置 像这样添加您的keymap.cson: 'atom-workspace': 'ctrl-x ctrl-b': 'buffer-list:show' ...
假装你是Xyzzy A Cards Against Humanity克隆,服务器和Web客户端。 有关完整的详细信息,请参见WebContent / license.html。 注意:该项目仅与Tomcat 7一起使用,不支持所有其他版本。 当前,构建PYX的唯一方法是...
如果你没有进一步了解元字符,可能不懂其中含义,不过没关系,在这里你只要知道,该代码的任务是显示电子邮箱dragon@xyzzy.com,用户名和组织名. Function SubMatchTest(inpStr) Dim oRe, oMatch, oMatches Set oRe = ...
默认摘要版本配置在xpasswd....digest ( "xyzzy" ) . then ( function ( key ) { console . log ( key ) ; // use Promise chaining to validate the password return validate ( "xyzzy" , key ) ; } ) .
Docker Your Xyzzy 启用您的Xyzzy: docker pull emcniece/dockeryourxyzzy : Docker Hub: 支持的标签和相应的Dockerfile链接: latest , 4 ( ) 什么是Docker Your Xyzzy? 这是“卡”克隆的容器化版本。...
Docker Your Xyzzy启用您的Xyzzy: docker pull emcniece/dockeryourxyzzy : Docker Hub: 支持的标签和相应的Dockerfile链接: latest , 4 ( )什么是Docker Your Xyzzy?这是“卡”克隆的容器化版本。 :warning...
var token = xforgot ( { secret : "xyzzy" , salt : "foobar" } ) ; // Send token to user via URL... if ( xforgot . verify ( { token : token , secret : "xyzzy" , salt : "foobar" } ) ) { // Reset the ...
YaTeX在DOS和Windows上的其他杰出编辑器上都有兄弟,Vz,Wz,Hidemaru,xyzzy.如果您使用YaTeX系列,您可以在任何平台上以相同的界面编写您的文档。 yahtml 是一个诚实和明亮的 YaTeX 兼容的主要模式包,用于编写 ...
YaTeX在DOS和Windows上的其他杰出编辑器上都有兄弟,Vz,Wz,Hidemaru,xyzzy.如果您使用YaTeX系列,您可以在任何平台上以相同的界面编写您的文档。 yahtml 是一个诚实和明亮的 YaTeX 兼容的主要模式包,用于编写 ...
名称 find_open_resolvers -- 在给定的 IP 范围内查找开放的 DNS 解析器。... --fqdn Fully Qualified Domain Name to query for (www.xyzzy.net) --verbose be verbose --help display brief help --man displa
假装你是Xyzzy A Cards Against Humanity克隆,服务器和Web客户端。 有关完整的详细信息,请参见WebContent / license.html。 注意:该项目仅与Tomcat 7一起使用,不支持所有其他版本。 当前,构建PYX的唯一方法是...
使用已实现的作弊功能(xyzzy + Shift + Enter)解决所有WinMine问题。 计算网格的大小并标记所有地雷。
从您最喜欢的编辑器运行Wandbox Vim: : Emacs的: : xyzzy: ://gist.github.com/kikairoya/7544234执照Boost软件许可1.0常问问题如果要添加编译器怎么办? 请求请求到 。如果我想向Wandbox添加功能怎么办?请将...
>>> packed = msgpack.packb(msgpack.ExtType(42, b'xyzzy')) >>> msgpack.unpackb(packed) ExtType(code=42, data='xyzzy') You can use it with ``default`` and ``ext_hook``. See below. Note for msgpack ...