AI 助理
备案控制台
开发者社区 人工智能 文章 正文

Runaway Robot游戏过关通用算法设计并java语言实现

2013-01-24 1218
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这是一个游戏，感觉不错，加上有固定的套路去寻找答案，所以就决定用程序实现。 这个小游戏的网址：点击打开链接        http://www.hacker.org/runaway/index.php 这个游戏是一个机器人在布满炸弹的地图（bigLayout）中寻找出路，出路是在雷区的边界（绿色区域）。但机器人（robot）记住的路途太少不可以记住从

这是一个游戏，感觉不错，加上有固定的套路去寻找答案，所以就决定用程序实现。

这个小游戏的网址：点击打开链接        http://www.hacker.org/runaway/index.php

这个游戏是一个机器人在布满炸弹的地图（bigLayout）中寻找出路，出路是在雷区的边界（绿色区域）。但机器人（robot）记住的路途太少不可以记住从开始到安全区域的所有路径。robot会记住最小（min）的路径步数和最大（max）的路劲步数，但走完了记忆步骤，就开始循环记忆步骤。robot只会两种走法（向右和向下），开始时的图形为下图：

 
下面说一下算法：
游戏<Runaway Robot>算法：
Input： int min  //最小步数
int max  //最大步数
String info //布局
Output：int path[][] //可行路径
1 do getBigLayout
2 for min to max：
for-each Dot，Dot为固定步骤一次循环到达的位置
if dot可用：
do getLayout
do getLayoutUse
do getLayoutCut
3 return：Layout
getBigLayout1 把info代表的信息转化为地图
getLayout：
1 dot位置，建立layout布局 2  依据bigLayout，丰满layout布局 ，即把到到达dot位置的步骤循环走完bigLayout，经过区域的炸弹全部映射到layout中，其中炸弹区为   标记为red，null标记为null
getLayoutUse： 1 初始化layout起点为green
2 for-each layout.dot，由上至下，由左到右遍历layout
if dot为green
感染dot的右一或下一位置为null的为green
3 return layout
getLayoutCut：
1 初始化layout结束点（右下方的点）为robot 2  for-each layout.dot，由下至上，由右到左遍历layout
if dot为robot
感染dot的左一或上一位置 为green 为 robot
3 return layout java算法实现： 注意：0,green;1,red;2,null;3,robot;
[java]  view plain copy
  1. package runaway;  
  2. public class Robot {  
  3.       
  4.     //主要算法实现  
  5.     public int[][] go(String info,int min,int max){  
  6.         int bigLayout[][]=getBigLayout(info);  
  7.         int layout[][]=null;  
  8.         for(int i=min;i<=max;i++){  
  9.             for(int j=0;j<=i;j++){  
  10.                 int I=i-j+1;  
  11.                 int J=j+1;  
  12.                 layout=getLayout(bigLayout,I,J);  
  13.                 layout=layoutUse(layout);  
  14.                 layout=layoutCut(layout);  
  15.                 if(layout!=null)  
  16.                     return layout;  
  17.             }  
  18.         }  
  19.         return null;  
  20.     }  
  21.   
  22.     //获取bigLayout  
  23.     private int[][] getBigLayout(String info){  
  24.         int n=(int)Math.sqrt((double)info.length());  
  25.         int bigLayout[][] =new int[n+1][n+1];  
  26.         for(int i=0;i<bigLayout.length;i++){  
  27.             for(int j=0;j<bigLayout[0].length;j++){  
  28.                 bigLayout[i][j]=2;  
  29.             }  
  30.         }  
  31.         int sum=0;  
  32.         for(int i=0;i<n;i++){  
  33.             for(int j=0;j<n;j++){  
  34.                 if(info.charAt(sum)=='X'){  
  35.                     bigLayout[i][j]=1;  
  36.                     sum++;  
  37.                 }else if(info.charAt(sum)=='.'){  
  38.                     bigLayout[i][j]=2;  
  39.                     sum++;  
  40.                 }else{  
  41.                     System.out.println("error:getBigLayout");  
  42.                     System.exit(0);  
  43.                 }  
  44.             }  
  45.         }  
  46.         return bigLayout;  
  47.     }  
  48.       
  49.     //获取layout  
  50.     private int[][] getLayout(int[][] bigLayout, int i, int j) {  
  51.         int layout[][]=new int[i][j];  
  52.         for(int x=0;x<layout.length;x++){  
  53.             for(int y=0;y<layout[0].length;y++){  
  54.                 layout[x][y]=2;  
  55.             }  
  56.         }  
  57.         for(int m=0;m<bigLayout.length;m++){  
  58.             for(int n=0;n<bigLayout[0].length;n++){  
  59.                 int M=m;  
  60.                 int N=n;  
  61.                 while(M>=(i-1) && N>=(j-1)){  
  62.                     M=M-i+1;  
  63.                     N=N-j+1;  
  64.                 }  
  65.                 if(M>=0 && M<i){  
  66.                     if(N>=0 && N<j){  
  67.                         if(bigLayout[m][n]==1){  
  68.                             layout[M][N]=1;  
  69.                         }else if(bigLayout[m][n]!=2){  
  70.                             System.out.println("error:getLayout!!");  
  71.                             System.exit(0);  
  72.                         }  
  73.                     }  
  74.                 }  
  75.             }  
  76.         }  
  77.         return layout;  
  78.     }  
  79.   
  80.     //获取layout，其中包括可行路径,可为null  
  81.     private int[][] layoutUse(int[][] layout) {  
  82.         if(layout[layout.length-1][layout[0].length-1]==1 || layout[0][0]==1)  
  83.             return null;  
  84.         if(layout[0][0]==2)  
  85.             layout[0][0]=0;  
  86.         else{  
  87.             System.out.println("error:layoutUse01");  
  88.             System.exit(0);  
  89.         }  
  90.         for(int i=0;i<layout.length;i++){  
  91.             for(int j=0;j<layout[0].length;j++){  
  92.                 if(layout[i][j]==0){  
  93.                     if((i+1)<layout.length && layout[i+1][j]==2){  
  94.                         layout[i+1][j]=0;  
  95.                     }  
  96.                     if((j+1)<layout[0].length && layout[i][j+1]==2){  
  97.                         layout[i][j+1]=0;  
  98.                     }  
  99.                 }  
  100.             }  
  101.         }  
  102.           
  103.         return layout;  
  104.     }  
  105.   
  106.     //获取layout，其中包括安全路径,可为null  
  107.     private int[][] layoutCut(int[][] layout) {  
  108.         if(layout==null)  
  109.             return null;  
  110.         if(layout[layout.length-1][layout[0].length-1]==0){  
  111.             layout[layout.length-1][layout[0].length-1]=3;  
  112.         }else{  
  113.             return null;  
  114.         }  
  115.         for(int i=layout.length-1;i>=0;i--){  
  116.             for(int j=layout[0].length-1;j>=0;j--){  
  117.                 if(layout[i][j]==3){  
  118.                     if((i-1)>=0 && layout[i-1][j]==0){  
  119.                         layout[i-1][j]=3;  
  120.                     }  
  121.                     if ((j-1)>=0 && layout[i][j-1]==0){  
  122.                         layout[i][j-1]=3;  
  123.                     }  
  124.                 }  
  125.             }  
  126.         }  
  127.         return layout;  
  128.     }  
  129. }  
此后，我们要在可行路径中选一条输出。具体实现代码入下：
[java]  view plain copy
  1. package test;  
  2. public class Look {  
  3.     public void look(int matrix[][]){  
  4.         int m=matrix.length;  
  5.         int n=matrix[0].length;  
  6.         int i=0;  
  7.         int j=0;  
  8.         while(j<=n&i<m){  
  9.             if((j+1)<n && matrix[i][j+1]==3){  
  10.                 System.out.print("右 ");  
  11.                 j++;  
  12.             }else{  
  13.                 i++;  
  14.                 if(i<m){  
  15.                     System.out.print("下 ");  
  16.                 }     
  17.             }  
  18.         }  
  19.     }  
  20. }  


java实现后，就是运行了。
首先是获取info信息，获取方法和内容如下：

其中灰色的value值后的值（本例为FVterrainString=.....X..X...XX.XX...... .......X....XX. ..X.X.X.....X....X.X....... X
...X. . . . ..X.....XXX.XX..X.........XXX......X....XX.....X.....X..X..X..X....X..X..XX.X.X..X.......X...XXX.XX...X...X.X.XX.XXXX.XX.X....X.X..XX..X...XX.............X.....X..XXX.XXX...XX..X..............X.X.....X.X....X.X.XXX.....X...........XX.X......X......XX..X.X..X..X....XX..X.X.XX...X...X.X...X.X.XX.XX..X..X.X..X..X......X..X..X....XX...X.X..............X...............X..X....XX..X..........X..X...X...X.X....XX...X......XX.....X...........X.XXXXX.......X..X..XXXX..X..........................X.X..X..X........X.....X..XX.X.X..X.XX..........XX.X..X.X......X.XX..XXX.XX.X.X.......X.X..........X........X.XX...XX....XX.X.XX..........XXXX....X...XXX.X.........X.X......X....X...............X.X.XXX..X..X.X..X.X...XX..XX.............X...........X......X.X.XX.....XX..X.....XXX....X.XX...XX...X.X.........X...............XX.....X......X...X.XXX.....XX.X.X.....X.....X....X............X.X....X....X......X..X.....XX..XX...................X....X......XX.........X.....X......X.X..XXXX.....XXX..........X.X.......X...........X.X.....X...........X.....X........X.........XX..XX.X...XX........X...X...XX.......X.XX....X...X....X........XX...XX............X.XX.X.....XX............XX..X......X.X..X......X.....X.X....X....X...XXXX.........X.XX.XXX.X......X.X.X...X........X.X.X........X...X.X..XX.X..X......X....X....X...X.......X..............X................X........X.......X.XX.XX...XXXX.X..X.XX.X..XX..X.X.........X...X.X...X...X.X..XX...XX........X.....XX...X..X..X.X....X...XX....XX....XX.X.X..XX...............X.....X...X....X.......X.......X..XX.X........XX...X..X..X..XX............X.X...X.XX...XX.....X..XX...X...............XX..XX.XX..X...X...X.......X........X.X.X...........X......X.....X.X......X....X.X..........X....X.......X............X.X......X.....X............XX..XX...X.X...XX......X.X...........X...X.X....X...X......XX....XX.X.XX.XXXX..X...........X...X.X......XX...XX.X...X.X....X.....X.X.XXX...XX..XXX....X...X...X.X.XX..XX.....X..XXXXXX.....X.XX...X.XX....XX.....X..X...XXX.....X.X.X.X..XX..X...X.XX.....X.............XX....X....X....X.X.......X..X.........X..XX......XXXXXX...X.........X...X....X...X.X.X..XX.XXX...XX.X.X.............X...XXX.........X.XXX.X........XX......X...XX..X.............XXX...XX.......X...........X.X..XX..X.....X...X.X...X........XX.XX...XXX..X.......X.X.X.....X....XXX.X.XX....X..XX.X.....X...X.....X.X...X.XX.X..X...XX.X....X.......X...XX...X......XX..X...X.....X......XXXX.X.....XX..X...X.........X.....X..X....XXX.....X........X..X..XX.XXX.....XX...........X........X...X.X..X..X.&FVinsMax=30&FVinsMin=18&FVboardX=51&FVboardY=51&FVlevel=96），“.”代表安全，"X"代表炸弹。其中min为 FVinsMin，max为FVinsMax。这些就可以在运行软件中得知。
现在编写运行代码如下： 
import java.util.Scanner;
import runaway.Robot;
import test.Look;


public class Test {

	public static void main(String[] args) {
		String info;
		int min;
		int max;
		while(true){
			System.out.println("input::");
			Scanner sc=new Scanner(System.in);
			String value=sc.nextLine();
			info=value.substring(value.indexOf("FVterrainString=")+16, value.indexOf("&FVinsMax="));
			String Max=value.substring(value.indexOf("&FVinsMax=")+10, value.indexOf("&FVinsMin="));
			String Min=value.substring(value.indexOf("&FVinsMin=")+10, value.indexOf("&FVboardX="));
			min=Integer.valueOf(Min);
			max=Integer.valueOf(Max);
			Robot bo=new Robot();
			int path[][]=bo.go(info,min,max);
			if(path==null){
				System.out.println("game over:null");
			}
			for(int [] x:path){
				for(int y:x){
					System.out.print(y+"  ");
				}
				System.out.println("");
			}
			new Look().look(path);
			System.out.println();
		}
		

	}

}


运行上述代码，在input::后面输入在网页源码中获取的信息，并回车确认。这样既可以得到运行结果。如下图：

根据运行结果，输入步骤的选择，最后就可以运行成功。输入并闯关成功的图片所示如下：

game over！！！

——fxleyu
20130115写于QQ空间
20130124在原有基础上增加Look类，实现结果的人性化显示。

文章标签：
算法
Java
机器人
安全
关键词：
Java语言
算法语言
算法java
Java游戏
游戏算法
风雪乐雨
目录
相关文章
java冯坚持
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
69 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
热爱技术的小郑
|
3月前
|
Java Maven
使用java语言制作一个窗体（弹窗），用来收集用户输入的内容
该博客文章介绍了如何使用Java Swing中的JFrame创建一个窗体来收集用户输入的内容，并提供了详细的实现步骤和完整代码示例。
热爱技术的小郑
168 2
使用java语言制作一个窗体（弹窗），用来收集用户输入的内容
众所周知
|
10天前
|
SQL 安全 Java
安全问题已经成为软件开发中不可忽视的重要议题。对于使用Java语言开发的应用程序来说，安全性更是至关重要
在当今网络环境下，Java应用的安全性至关重要。本文深入探讨了Java安全编程的最佳实践，包括代码审查、输入验证、输出编码、访问控制和加密技术等，帮助开发者构建安全可靠的应用。通过掌握相关技术和工具，开发者可以有效防范安全威胁，确保应用的安全性。
众所周知
23 4
nanshaws
|
1月前
|
开发框架 IDE Java
java制作游戏，如何使用libgdx，入门级别教学
本文是一篇入门级教程，介绍了如何使用libgdx游戏开发框架创建一个简单的游戏项目，包括访问libgdx官网、设置项目、下载项目生成工具，并在IDE中运行生成的项目。
nanshaws
48 1
java制作游戏，如何使用libgdx，入门级别教学
龙大吉
|
1月前
|
Java 程序员 编译器
在Java编程中，保留字（如class、int、for等）是具有特定语法意义的预定义词汇，被语言本身占用，不能用作变量名、方法名或类名。
在Java编程中，保留字（如class、int、for等）是具有特定语法意义的预定义词汇，被语言本身占用，不能用作变量名、方法名或类名。本文通过示例详细解析了保留字的定义、作用及与自定义标识符的区别，帮助开发者避免因误用保留字而导致的编译错误，确保代码的正确性和可读性。
龙大吉
42 3
G0518
|
1月前
|
移动开发 Java 大数据
深入探索Java语言的核心优势与现代应用实践
【10月更文挑战第10天】深入探索Java语言的核心优势与现代应用实践
G0518
51 4
喜欢猪猪
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题，java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中，分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效，业界提出了多种解决方案，其中雪花算法（Snowflake Algorithm）是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法，并提供Java代码示例。
喜欢猪猪
67 2
dream_ready
|
1月前
|
存储 Java 数据安全/隐私保护
Java中的域，什么是域？计算机语言中的域是什么？(有代码实例)
文章解释了Java中域的概念，包括实例域、静态域、常量域和局部域，以及它们的特点和使用场景。
dream_ready
54 2
兴化
|
1月前
|
Java 数据安全/隐私保护 C++
Java语言关键字
Java语言关键字
兴化
22 2
派大鑫的工作室
|
1月前
|
分布式计算 安全 Java
Java语言的特点？
Java语言的特点？
派大鑫的工作室
38 0

热门文章

最新文章

  • 1
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 2
    算法学习之顺序结构
  • 3
    泛型KMP算法
  • 4
    【算法】算法之美—Fire Net
  • 5
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 6
    字符串相似度算法 递归与动态规划求解分析
  • 7
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 8
    【算法研究】Bresenham画线算法
  • 9
    梯度下降算法详解（从下山比喻、数学推导到代码实现）
  • 10
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 1
    Dubbo03【管理控制台和监控中心搭建】，Java开发实用必备的几款插件
    56
  • 2
    Java中int[]与Integer[]相互转化的方法，java基础知识面试重点总结
    35
  • 3
    Java 并发编程中的锁优化策略
    34
  • 4
    Java一分钟之-设计模式：装饰器模式与代理模式
    63
  • 5
    《手把手教你》系列技巧篇（四十六）-java+ selenium自动化测试-web页面定位toast-下篇（详解教程）
    63
  • 6
    刷题两个月，从入门到字节跳动offer丨GitHub标星16k+，美团Java面试题
    65
  • 7
    《MySQL 入门教程》第 05 篇 账户和权限，Java高并发编程详解深入理解pdf
    53
  • 8
    Java的前景如何，好不好自学？，万字Java技术类校招面试题汇总
    54
  • 9
    es集群安装，邮储银行java面试
    79
  • 10
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    98

    • 相关课程

    更多
  • Java零基础入门
  • 5天玩转Java面向对象编程
  • Java开发工具
  • 神经网络概览及算法详解
  • Java 虚拟机原理
  • Java Web项目实战 - 图书商城

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 语言入门-1：环境构建
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • Python网络通信程序典型应用
    • 下一篇
    阿里云OSS设置跨域访问