文章目录

  Sokoban即我们小时候玩过的推箱子游戏,Sokoban pathfinding,即根据指定的输入地图找到正确的路径。

  这也是学期开始的时候付贵找我跟他一起倒腾的。

  我直接从他们学校的网站把题目爬过来,有兴趣的可以看一看。

  In this homework you will implement a building block to use in the Sokoban project. This is an individual assignment and as the name implies a test of your basic programming skills. Unless you find the task simple you should reconsider the choice of course or brush up on the programming and algorithmic skills that are prerequisites of this course. You need to finish this assignment before you are allowed to join a project group. The rationale behind this is that unless you can solve this problem you will not be able to contribute to the work of the project group in a fair way.

  A sokoban map is a two-dimensional grid that contains walls, boxes, goals and one player, as seen in the figure /reffig:ex. The target of the game is to push the boxes onto the goals. In this assignment, however, your target is simpler. You just need to move the player to any goal WITHOUT pushing any boxes.

  Figure 1: A graphical illustration of a sokoban map. There is one player, N boxes and goals. In this assignment the task is to find a path from the start position of the player to one of the goals WITHOUT moving any boxes.

Input

  Your agent program will get as an input a board as a string where each character represents one cell. Each cell will be one of the following symbols:

’ ’

Free space

’#’

Wall

’.’

Goal

’@’

Sokoban player

’+’

Sokoban player on goal

’$’

Box

’*’

Box on goal

  To be more concrete if “map1.txt” is a file with a sokoban map your agent program “agent” will get map1.txt sent to in on standard input. Under unix/linux this corresponds to running the program like

  agent < map1.txt

Output

  You should output (on standard output) a string of player movements (composed of a sequence of the characters “U” for up, “D” for down, “L” for left and “R” for right). After the moves are executed, the player should stand on a goal. No boxes can be moved!

  As an example, if your client receives the board in figure 1, URRRRRRR would be a correct answer. That is, move up one time and then move to the right a bunch of times until you reach the goal locations. We are not requiring your agent to find the shortest solution, so URRLRLRLRRRRRRRDUU would also be correct. If no goal is reachable, the output should be ’no path’ (exactly like that). If the player already is on a goal, the output string may be empty as no moves are needed to reach the goal. For more examples, see below.

  Your program must find the path to all maps provided with 1 second.

Sample Input 1

########
#   # .#
#   $$.#
####   #
   #@ ##
   ####

Sample Output 1

U R R U

Sample Input 2

########
#   # .#
#$*#
####   #
   #@ ##
   ####

Sample Output 2

no path

Sample Input 3

########
#   # .#
#   $$+#
####   #
   #  ##
   ####

Sample Output 3

player already on goal

Download the sample data files

题目比较简单,直接贴代码:

package sokoban;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;
public class Sokoban {
static int starty = 0;
static int startx = 0;
int endy = 0;
int endx = 0;
static Stack<Object> st = new Stack<Object>();
static Stack<String> vector = new Stack<String>();
int flag = 0;
static Vector<String> board = new Vector<String>();
static ArrayList<String> al = new ArrayList<String>();

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    boolean isend = false;
    String line;
    Scanner sc = new Scanner(System.in);
    while (!"over".equals(line = sc.nextLine())) {
        board.add(line);
    }
    boolean playerOnGoal = playerOnGoal();
    if (playerOnGoal == false) {
        boolean haveGamer = haveGamer();

        if (haveGamer == false) {
            System.out.println("No Gamer");
        }

        else if (findTR() == true || findTL() == true || findBR() == true
                || findBL() == true) {
            for (int i = 0; i < al.size(); i++) {
                System.out.print(al.get(i).toString());

            }
            al.clear();
            st.clear();
        } else if ((findTR() == false && findTL() == false
                && findBR() == false && findBL() == false)
                && haveGamer == true) {
            System.out.println("no path");
        }

    } else {
        System.out.println("player already on goal");
    }
}

public static boolean findTR() {
    boolean find = false;
    int bool = 0;
    int j = 0;
    int checkstartx = startx;
    int disX = 0;
    int disY = 0;

    for (int i = starty; i > 0; i--) {
        if (bool == 1) {
            break;
        }
        vector.push("U");
        char[] a = board.get(i).toCharArray();
        j = checkstartx;
        for (; j < a.length; j++) {

            if (st.size() > 1) {
                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    disX = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    disY = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }
            }

            String carrier = String.valueOf(a[j]);

            if (carrier.equals(" ")) {
                st.push(j + " ," + i);
                if (j > checkstartx) {
                    al.add("R");
                }
            } else if (disX > 1 || disY > 1) {
                bool = 1;
                break;
            } else if (carrier.equals(".")) {
                st.push(j + " ," + i);
                bool = 1;

                int x = 0;
                int y = 0;

                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    x = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    y = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }

                if (x == 1 && y == 0) {
                    al.add("R");
                } else if (x == 0 && y == 1) {
                    al.add("U");
                }
                find = true;
                break;
            } else if (carrier.equals("#") || carrier.equals("*")
                    || carrier.equals("$")) {
                checkstartx = j - 1;
                al.add("U");
                break;
            }

        }
    }
    return find;
}

public static boolean playerOnGoal() {
    boolean goal = false;
    for (int i = 0; i < board.size(); i++) {
        char[] a;
        a = board.get(i).toCharArray();
        for (int j = 0; j < a.length; j++) {
            String ind = String.valueOf(a[j]);
            if (ind.equals("+")) {
                goal = true;
                break;
            }
        }

    }
    return goal;
}

public static boolean haveGamer() {
    boolean gamer = false;
    for (int i = 0; i < board.size(); i++) {
        char[] a;
        a = board.get(i).toCharArray();
        for (int j = 0; j < a.length; j++) {
            String ind = String.valueOf(a[j]);
            if (ind.equals("@")) {
                starty = i;
                startx = j;
                gamer = true;
                break;
            }
        }

    }
    return gamer;
}

public static boolean findBR() {
    boolean find = false;
    int bool = 0;
    int j = 0;
    int checkstartx = startx;
    int disX = 0;
    int disY = 0;

    for (int i = starty; i < board.size(); i++) {
        if (bool == 1) {
            break;
        }
        char[] a = board.get(i).toCharArray();
        j = checkstartx;
        for (; j < a.length; j++) {
            if (st.size() > 1) {
                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    disX = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    disY = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }
            }

            String carrier = String.valueOf(a[j]);
            if (carrier.equals(" ")) {
                st.push(j + " ," + i);
                if (j > checkstartx) {
                    al.add("R");
                }
            } else if (disX > 1 || disY > 1) {
                bool = 1;
                break;
            } else if (carrier.equals(".")) {
                st.push(j + " ," + i);
                bool = 1;
                System.out.println("Find!");
                int x = 0;
                int y = 0;

                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    x = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    y = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }

                if (x == 1 && y == 0) {
                    al.add("R");
                } else if (x == 0 && y == 1) {
                    al.add("D");
                }

                find = true;
                break;
            } else if (carrier.equals("#") || carrier.equals("*")
                    || carrier.equals("$")) {
                checkstartx = j - 1;
                al.add("D");
                break;
            }
        }
    }

    return find;
}

public static boolean findTL() {
    boolean find = false;
    int bool = 0;
    int j = 0;
    int checkstartx = startx;
    int disX = 0;
    int disY = 0;

    for (int i = starty; i > 0; i--) {
        if (bool == 1) {
            break;
        }
        char[] a = board.get(i).toCharArray();
        j = checkstartx;
        for (; j > 0; j--) {
            if (st.size() > 1) {
                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    disX = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    disY = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }
            }

            String carrier = String.valueOf(a[j]);
            if (carrier.equals(" ")) {
                st.push(j + " ," + i);
                if (j < checkstartx) {
                    al.add("L");
                }
            } else if (disX > 1 || disY > 1) {
                bool = 1;
                break;
            } else if (carrier.equals(".")) {
                st.push(j + " ," + i);
                bool = 1;
                System.out.println("Find!");
                int x = 0;
                int y = 0;

                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");
                    x = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    y = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }

                if (x == 1 && y == 0) {
                    al.add("L");
                } else if (x == 0 && y == 1) {
                    al.add("U");
                }

                find = true;
                break;
            } else if (carrier.equals("#") || carrier.equals("*")
                    || carrier.equals("$")) {
                checkstartx = j - 1;
                al.add("U");
                break;
            }
        }
    }

    return find;
}

public static boolean findBL() {
    boolean find = false;
    int bool = 0;
    int j = 0;
    int checkstartx = startx;
    int disX = 0;
    int disY = 0;

    for (int i = starty; i < board.size(); i++) {
        if (bool == 1) {
            break;
        }
        char[] a = board.get(i).toCharArray();
        j = checkstartx;
        for (; j > 0; j--) {
            if (st.size() > 1) {
                for (int k = 1; k < st.size(); k++) {
                    String[] line1 = st.get(k).toString().split(" ,");
                    String[] line2 = st.get(k - 1).toString().split(" ,");

                    disX = Math.abs(Integer.valueOf(line1[0])
                            - Integer.valueOf(line2[0]));
                    disY = Math.abs(Integer.valueOf(line1[1])
                            - Integer.valueOf(line2[1]));
                }
            }

            String carrier = String.valueOf(a[j]);
            if (carrier.equals(" ")) {
                st.push(j + " ," + i);
                if (j < checkstartx) {
                    al.add("L");
                }
            } else if (disX > 1 || disY > 1) {
                bool = 1;
                break;
            } else if (carrier.equals(".")) {
                st.push(j + " ," + i);
                bool = 1;
                System.out.println("Find!");
                find = true;
                break;
            } else if (carrier.equals("#") || carrier.equals("*")
                    || carrier.equals("$")) {
                checkstartx = j - 1;
                al.add("D");
                break;
            }
        }
    }

    return find;
}
}

  实例的验证如下:

  如果需要处理地图文件data文件的话,直接IO操作读入后再处理,不再赘述。


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录