从类似棋盘的迷宫中找起点到终点的最短路径代码,Java代码库,德仔网

代码语言
代码分类
【Java】从类似棋盘的迷宫中找起点到终点的最短路径
作者: / 发布于2013/10/11/ 539

	package ai.assignment1;

	import java.util.Scanner;

	public class Test {
	static String path = "";
	static int[][] map = new int[7][7];
	public static int[] funcB(int[] position) {
	
	 // 找一条最短路径的方法
	 int x = position[0];
	 int y = position[1];
	 int nextPosition[] = { x, y };

	 // up is the next point
	 if (x - 1 >= 0 && map[x - 1][y] + 1 == map[x][y]) {

	 // ----------------------------------------------
	 {
	 x = x - 1;
	 path = path + " (" + Integer.toString(x) + ","
	 + Integer.toString(y) + ") ";
	 nextPosition[0] = x;
	 nextPosition[1] = y;
	 funcB(nextPosition);
	 }
	 } else if (y + 1 <= 6 && map[x][y + 1] + 1 == map[x][y]) {
	 y = y + 1;
	 path = path + " (" + Integer.toString(x) + ","
	 + Integer.toString(y) + ") ";
	 nextPosition[0] = x;
	 nextPosition[1] = y;
	 funcB(nextPosition);
	 } else if (x + 1 <= 6 && map[x + 1][y] + 1 == map[x][y]) {
	 x = x + 1;
	 path = path + " (" + Integer.toString(x) + ","
	 + Integer.toString(y) + ") ";
	 nextPosition[0] = x;
	 nextPosition[1] = y;
	 funcB(nextPosition);
	 } else if (y - 1 >= 0 && map[x][y - 1] + 1 == map[x][y]) {
	 y = y - 1;
	 path = path + " (" + Integer.toString(x) + ","
	 + Integer.toString(y) + ") ";
	 nextPosition[0] = x;
	 nextPosition[1] = y;
	 funcB(nextPosition);
	 }

	 return null;
	}

	public static void main(String[] args) {
	
	 //Smiley smiley = new Smiley();

	 // 设置地图初始值为-1
	 for (int i = 0; i < 7; i++) {
	 for (int j = 0; j < 7; j++) {
	 map[i][j] = -1;
	 }
	 }
	 // initialize the map
	 // -1 empty ;-2 obstacle ;0 home
	 // Obstacles
	 map[0][3] = -2;
	 map[1][1] = -2;
	 map[1][4] = -2;
	 map[2][1] = -2;
	 map[2][4] = -2;
	 map[3][1] = -2;
	 map[3][2] = -2;
	 map[3][4] = -2;
	 map[4][2] = -2;
	 map[5][2] = -2;
	 map[5][3] = -2;
	 map[5][4] = -2;
	 // Home ■
	 map[3][3] = 0;

	 // Information
	 System.out
	 .println("\nArtificial Intelligence Assignment 1 \nName:Zhiheng Yi, Chen Chen, Jingtian Zhao");
	 System.out
	 .println("\nThis program is based on an algorithm which is used to find the shortest path from starting point to home.");
	 System.out
	 .println("It can be used in not only this specific maze but also any kinds of mazes.");
	 System.out
	 .println("You can choose any points on maze and set them as start point, end point and obstacle points.\n");
	 System.out
	 .println("This maze can be viewed as a 7*7 matrix. And the coordinate of top-left point is (0,0). The home is (3,3).\n");

	 // Print matrix
	 for (int i = 0; i <= 6; i++) {
	 for (int t = 0; t <= 6; t++) {
	 System.out.print("|(" + i + "," + t + ")");
	 }
	 System.out.print("|");
	 System.out.println("");
	 }
	 System.out
	 .println("\nIn addition, you can choose any points on maze as start point. And the program will show you the shortest path.\n");

	 // 设置地图，计算最短路程并填满地图
	 int k = 36;
	 int a, b, p, q = 0;
	 for (a = 0, b = 1; k > 0; a++, b++) {
	 for (int i = 0; i < 7; i++) {
	 for (int j = 0; j < 7; j++) {
	 if (map[i][j] == a) {
	 for (p = 0; p < 7; p++) {
	 for (q = 0; q < 7; q++) {
	 if ((p == i && q == j - 1)
	 || (p == i && q == j + 1)
	 || (p == i - 1 && q == j)
	 || (p == i + 1 && q == j)) {
	 if (map[p][q] == -1) {
	 map[p][q] = b;
	 k--;
	 }

	 }

	 }
	 }
	 }
	 }
	 }
	 }

	 // set original graphic map
	 System.out
	 .println("The original map(The black blocks are obstacles, the triangle is the home)\n");
	 for (int i = 0; i <= 6; i++) {
	 for (int j = 0; j <= 6; j++) {
	 // System.out.print("|(" + i + "," + j + ")");
	 if (map[i][j] == -2) {
	 System.out.printf("|■");
	
	 } else if (map[i][j] == 0) {
	 System.out.print("|▲");
	 } else {
	 System.out.printf("| ");
	 }
	 }
	 System.out.print("|");
	 System.out.println("");
	 }

	 while (1 == 1) {

	 Scanner s = new Scanner(System.in);

	 System.out.println("\nPlease choose:");
	 System.out.println("1.Input the location of the smiley");
	 System.out.println("2.Print the current map");
	 System.out.println("3.Caculate the optimal path");
	 System.out.println("4.Show the result of h(x)");
	 System.out.println("5.Close the program");

	 String str = s.next();

	 if (str.equals("1")) {
	 int x, y = 0;
	 System.out.println("Please input the X coordinate of smiley.");
	 x = (Integer) s.nextInt();
	 System.out.println("Please input the Y coordinate of smiley.");
	 y = (Integer) s.nextInt();
	 System.out
	 .println("The location of smiley has been setted as X:"
	 + x + " Y:" + y + " \n");
	 if (map[x][y] == -2) {
	 System.out.println("This point is a obstacle point.\n");
	 } else if (map[x][y] == 0) {
	 System.out.println("This point is the ending point.\n");
	 } else {
	 System.out
	 .println("The length from this point to the end is "
	 + map[x][y]);
	 System.out.println("The one of the nearest paths is ");
	 int position[] = { x, y };
	 funcB(position);
	 System.out.println(path);

	 }

	 } else if (str.equals("2")) {
	 // 打印地图
	 for (int i = 0; i <= 6; i++) {
	 for (int t = 0; t <= 6; t++) {
	 System.out.printf("%4s",+ map[i][t] + "|");
	 }
	 System.out.println();
	 }
	 } else if (str.equals("3")) {

	 } else if (str.equals("4")) {

	 } else if (str.equals("5")) {
	 break;
	 } else {
	 System.out.println("Wrong input.\n");
	 }

	 }

	}
	}
试试其它关键字
　最短路径　
同语言下
可能有用的
贡献的其它代码Label