小青蛙迷宫

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int p = in.nextInt();
Main main = new Main(n, m, p);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            main.maze[i][j] = in.nextInt();
        }
    }

    main.seek();

    if (main.res == null) {
        System.out.println("Can not escape!");
    } else {
        StringBuilder builder = new StringBuilder();
        for (Path path : main.res) {
            builder.append("[" + path.x + "," + path.y + "],");
        }
        String s = builder.toString();
        System.out.println(s.substring(0, s.length() - 1));
    }
}

public Main(int n, int m, int p) {
    this.n = n;
    this.m = m;
    this.p = p;
    maze = new int[n][m];
    mark = new boolean[n][m];
    minCost = p + 1;
}

static int[][] MOVE = new int[][] {
    new int[]{-1, 0, 3},
    new int[]{1, 0, 0},
    new int[]{0, -1, 1},
    new int[]{0, 1, 1}
};

int n, m, p;
int[][] maze;
boolean[][] mark;
int minCost;

List<Path> cur = new ArrayList<Path>();
List<Path> res = null;

public void seek() {
    if (cur.size() == 0) {
        cur.add(new Path(0, 0, 0));
        mark[0][0] = true;
    }
    Path curPath = cur.get(cur.size() - 1);
    if (curPath.x == 0 && curPath.y == m - 1) {
        int cost = 0;
        for (Path p : cur) {
            cost += p.cost;
        }
        if (cost < minCost) {
            res = new ArrayList<Path>(cur);
        }
    }
    for (int i = 0; i < MOVE.length; i++) {
        Path next = new Path(curPath.x + MOVE[i][0], curPath.y + MOVE[i][1], MOVE[i][2]);
        if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m
                && !mark[next.x][next.y] && maze[next.x][next.y] == 1) {
            cur.add(next);
            mark[next.x][next.y] = true;
            seek();
            cur.remove(cur.size() - 1);
            mark[next.x][next.y] = false;
        }
    }
}

}

class Path {
int x;
int y;
int cost;

public Path(int x, int y, int cost) {
    this.x = x;
    this.y = y;
    this.cost = cost;
}

@Override
public String toString() {
    return "Path{" +
            "x=" + x +
            ", y=" + y +
            ", cost=" + cost +
            '}';
}

}