传说问题是这样的
玩过KOF(拳皇)的人都知道,玩的时候会连招是比较强的。题目的大概意思是:每招用一个大写字母表示,如ABC...Z,现给定n个连招公式:S→T,其中S长度为m,T的长度为1。在前m招的时候可以随便连,但m+1招后就必须遵循连招公式。现在要写一个算法,计算最长连招的长度;如果可以无限连招,则返回def。1≤n,m≤100
给了一个例子:n=4,m=3,连招公式为:ABC→C,ABC→D,CCA→A,BCC→A。连招公式的意思是:A、B、C可以连出C,也可连出D,C、C、A可以连出A,B、C、A、可以连出B。这时候可以得到最长连招公式:ABC→C→A→A,即最长连招公式长度为6。
放十一长假闲着无聊,想了想具体解法;长假结束后抽出时间把算法完整写出来了。
首先是将问题转变成图论问题,需要将n中的每一个连招转化成图的邻接矩阵表示
ABC→C,ABC→D,CCA→A,BCC→A
转化成图的邻接矩阵为
0,0,0,1
0,0,0,0
0,0,0,0
0,0,1,0
(第一行0,0,0,1表示招式ABC-C后可以接BCC-A,第二行0,0,0,0表示ABC-D不能接任何连招,依次类推)
那么,首先判断是否def,即查找图中是否存在环,应用环中有反向边的定理(参照算法导论第22章:图的基本算法)
其查找def的关键代码如下
private boolean isDef() {
initGraph();
for (int i = 0; i < hits.length; i++) {
if (color[i].equals(Colors.WHITE)) {
dfs(i);
}
}
return isDef;
}
private void dfs(int index) {
color[index] = Colors.GRAY;
List<Integer> adj = getNextHits(index);
for (int i = 0; i < adj.size(); i++) {
if (color[adj.get(i)].equals(Colors.WHITE)) {
dfs(adj.get(i));
}
if (color[adj.get(i)].equals(Colors.GRAY)) {
isDef = true;
}
}
color[index] = Colors.BLACK;
}
如果是非def的
那么求最长连招,需要找到矩阵中的全0行,进行逆向BFS,并同时维护一个最长连招数组。
其关键代码如下
int[] maxHits = new int[hits.length];
for (int i = 0; i < list.size(); i++) {
Queue<Integer> queue = new Queue<Integer>();
queue.add(list.get(i));
maxHits[list.get(i)] = 1;
while (!queue.isEmpty()) {
int index = queue.front();
queue.delete();
List<Integer> adj = getPrevious_Hits(index);
for (int j = 0; j < adj.size(); j++) {
if (maxHits[adj.get(j)] < maxHits[index] + 1) {
maxHits[adj.get(j)] = maxHits[index] + 1;
queue.add(adj.get(j));
}
}
}
}
int max = 0;
for (int i = 0; i < maxHits.length; i++) {
if (maxHits[i] > max) {
max = maxHits[i];
}
}
具体可执行代码见附件。
PS1: 测试较少,希望童鞋们能提供更多的测试用例
PS2:getPrevious Hits这个方法,由于河蟹的佳爱不允许出现s-H-i-t这种不河蟹的单词,只能拆分为getPrevious_Hits,佳爱的河蟹词过滤该加油了
分享到:
相关推荐
[整理]永久性的解决Google Earth谷歌地球无法连接服务器问题
ES连接(谷歌插件)
谷歌地图GoogleMaps3.310 谷歌地图GoogleMaps3.310 谷歌地图GoogleMaps3.310 谷歌地图GoogleMaps3.310
软件名称:谷歌安装器 软件版本:v1.3.3 软件语言:中文 软件大小:9.82M 测试机型:三星 i9300 【软件介绍】 手机缺少谷歌市场和谷歌服务,很多大型精品游戏因为验证失败而...2.修复部分机型无法登录google play问题
谷歌商店上架流程,近两年,出海潮日渐兴起,游戏、短视频、社交等各个行业都在准备走向世界。而咱们国内的Android程序员素有“折翼天使”的名号,做了多年的Android开发,却不知道怎么成为Google Play开发者。 今天...
Android手机零基础/新手使用方法 LG nexus5 LG nexus5X Nexus 6P Pixel Pixel2 Pixel3 Pixel4 Pixel5 ...以上Google系列Android手机,Android系统无法联网问题的解决方法,超详细的使用方法和步骤!
google maps v5.10-ownhere中国加速版(定位+导航),解决了因为IP被封出现的“网络连接失败问题”。 Google地图“网络连接失败 此程序需要有效的数据连接”是因为其使用了Https连接,国内的服务器不支持此链接所致...
Explore advanced concepts of environmental understanding using Google ARCore and OpenGL ES with Java Create light levels from ARCore and create a C# script to watch and propagate lighting changes in a...
Google Chrome 谷歌浏览器 7.0.517.44 离线安装包
从谷歌商店下载的,支持安卓5.1及以上,谷歌出品
2022 Google翻译修复工具 V1.3 【谷歌浏览器无法翻译网页问题解决】 10月份,Google翻译API被误伤,官方干脆直接停用了。虽然网页翻译给停用了,但是API并没有停,稍微修改一下host就能解决。 鉴于使用不方便,...
谷歌地球最新版(Google Earth)是一款Google(谷歌)公司开发的虚拟地球仪软件,谷歌地球最新版整合Google的本地搜索以及驾车指南两项服务,谷歌地球能够鸟瞰世界。欢迎下载最新版本谷歌地球最新版(Google Earth)。谷歌...
谷歌镜像PHP虚拟主机版是一个以php+mysql进行开发的google镜像源码。 镜像站用Nginx很简单就可以做出来,但是虚拟主机用户就没办法修改Nginx了。 如果你用的是虚拟主机,这个程序上传之后解压到更目录就可以使用,...
近日将Google Wifi更新到9202.35.8版本之后,一些Google Wifi用户称其设备经常出现连接频繁中断问题,而修复只能暂时解决问题,下面就详情来看看了解下吧
Linux离线安装谷歌,参考链接:https://blog.csdn.net/lqh_linux/article/details/121078073
google chorme 谷歌 浏览器
GoogleCalendarSync 谷歌日历同步
谷歌地球最新版(Google Earth)是一款Google(谷歌)公司开发的虚拟地球仪软件,谷歌地球最新版整合Google的本地搜索以及驾车指南两项服务,能够鸟瞰世界。欢迎下载最新版本谷歌地球最新版(Google Earth)。 Google ...
解决: idea插件translation无法使用谷歌翻译(报错)问题
谷歌原生系统的键盘,原来是在Nexus上的键盘,供大家娱乐,下载下来玩玩,支持滑动输入,非常华丽。