地下迷宫

import java.util.Scanner;

// 回溯： m,n很小不超过10 + 要求具体路径

public class Main {
    private static String res = "Can not escape!"; // 结果：体力消耗最小路径
    private static int rest = -1; // 逃出迷宫时剩余体力
    private static StringBuilder path = new StringBuilder(); // 一次路径
    private static int[][] dxy = {{-1, 0, -3}, {0, 1, -1}, {1, 0, 0}, {0, -1, -1}}; // 上下左右 + 体力消耗

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), p = in.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        dfs(grid, 0, 0, p);

        System.out.println(res);
    }

    // 回溯
    private static void dfs(int[][] grid, int x, int y, int p) {
        int n = grid.length, m = grid[0].length;
        if (p < 0 || x == 0 && y == m - 1) {
            if (p >= 0 && x == 0 && y == m - 1) {
                if (p > rest) {
                    rest = p;
                    res = "[0,0]," + path.deleteCharAt(path.length() - 1).toString();
                }
            }
        }

        for (int i = 0; i < dxy.length; i++) {
            int dx = x + dxy[i][0], dy = y + dxy[i][1], cost = dxy[i][2];
            if ( dx < 0 || dy < 0 || dx >= n || dy >= m || grid[dx][dy] == 0) continue;
            String copy = path.toString();
            grid[dx][dy] = 0;
            path.append("[").append(dx).append(",").append(dy).append("],");
            dfs(grid, dx, dy, p + cost);
            grid[dx][dy] = 1;
            path = new StringBuilder(copy);
        }
    }

}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int n, m;
    static List<Integer[]> list = new ArrayList<>();
    static boolean[][] bool;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        int p = in.nextInt();
        int[][] mi = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mi[i][j] = in.nextInt();
            }
        }
        bool = new boolean[n][m];
        boolean b = get(mi, 0, 0, p);
        String result = "";
        if (b) {
            for (int i = list.size() - 1; i >= 0; i--) {
                Integer[] integers = list.get(i);
                result += "[";
                result += integers[0];
                result += ",";
                result += integers[1];
                result += "]";
                result += ",";
            }
            String substring = result.substring(0, result.length() - 1);
            System.out.println(substring);
        } else {
            System.out.println("Can not escape!");
        }


    }
    public static boolean get(int[][] mi, int l, int r, int p) {
        bool[l][r] = true;
        if (p >= 0 && (l == 0 && r == m - 1)) {
            Integer[] ints = new Integer[2];
            ints[0] = l;
            ints[1] = r;
            list.add(ints);
            return true;
        }
        //向右
        if (r + 1 <= m - 1 && mi[l][r + 1] != 0 && !bool[l][r + 1]) { //向右
            if (get(mi, l, r + 1, p - 1)) {
                Integer[] ints = new Integer[2];
                ints[0] = l;
                ints[1] = r;
                list.add(ints);
                return true;
            }
        }
        //向下
        if (l + 1 <= n - 1 && mi[l + 1][r] != 0 && !bool[l + 1][r]) {
            if (get(mi, l + 1, r, p)) {
                Integer[] ints = new Integer[2];
                ints[0] = l;
                ints[1] = r;
                list.add(ints);
                return true;
            }
        }
        //向上
        if (l - 1 >= 0 && mi[l - 1][r] != 0 && !bool[l - 1][r]) {
            if (get(mi, l - 1, r, p - 3)) {
                Integer[] ints = new Integer[2];
                ints[0] = l;
                ints[1] = r;
                list.add(ints);
                return true;
            }

        }
        //向左
        if (r - 1 >= 0 && mi[l][r - 1] != 0 && !bool[l][r - 1]) {
            if (get(mi, l, r - 1, p - 1)) {
                Integer[] ints = new Integer[2];
                ints[0] = l;
                ints[1] = r;
                list.add(ints);
                return true;
            }
        }

        bool[l][r] = false;
        return false;
    }

}

import java.util.*;
public class Main{	//递归,调了一个多小时，终于gc了
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();    //输入
            int m = sc.nextInt(); 
            int p = sc.nextInt();
            int[][] nums = new int[n][m];
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    nums[i][j] = sc.nextInt();
                }
            }
            jump(0, 0, nums, p); //逃走
            if(!res.isEmpty()){ //可以到达
                for(int i = 0;i < res.size() - 1;i++){
                    System.out.print("[" + res.get(i)[0] + "," + res.get(i)[1]+ "]" +",");
                }
                System.out.print("[" + res.get(res.size() - 1)[0] + "," + res.get(res.size() - 1)[1]+ "]");
            }else{
                System.out.print("Can not escape!");
            }
        }
        sc.close();
    }
    static ArrayList<int[]> path = new ArrayList<>();
    static ArrayList<int[]> res = new ArrayList<>();
    static int minP = 0;
    
    public static void jump(int i,int j,int[][] nums,int p){
    	if(i < 0 || i > nums.length - 1 || j < 0 || j > nums[0].length - 1 
    	           || nums[i][j] == 0 || p < 0)    //体力没了也GG
            return;
        if(i == 0 && j == nums[0].length - 1 && p >= minP){
            minP = p;
            path.add(new int[]{i,j}); //加入最后一个点
            res = new ArrayList<>(path);
            return;
        }
        nums[i][j] = 0; //走过
        path.add(new int[]{i,j}); //加入
        jump(i, j + 1, nums, p - 1); //向右
        jump(i - 1, j, nums, p - 3); //向上
        jump(i + 1, j, nums, p); //向下
        jump(i, j - 1, nums, p - 1); //向左
        nums[i][j] = 1; //回去
        path.remove(path.size() - 1);
    }
}

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    //n: 迷宫的行数  m:迷宫的列数  maxRemainEnergy: 剩余的能量数   maze： 迷宫地图（二维数组表示）
    // falg ： 能否完成任务标记符  list： 储存任务过程通过的点（数组下标位置）  listCopy： 记录上一次通过的点顺序
    static int n, m, maxRemainEnergy = -1;
    static int[][] maze;
    static boolean flag = false;
    static LinkedList<String> list = new LinkedList<>();
    static LinkedList<String> listCopy = new LinkedList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int p = scanner.nextInt();
        maze = new int[n][m];
        //建立二维数组 迷宫
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }
        //寻找最短路径的方法（递归处理）
        optimalPath(0,0, p);
        //判断能否完成任务
        if (!flag) {
            System.out.println("Can not escape!");
        } else {
            printPoint(maze);
        }
    }

    private static void optimalPath(int x, int y, int energy) {
        //(0,0) ----> (0,m-1)
        //如果能量耗尽或者超出地图的范围或者此路不通则返回
        if (energy < 0 || x<0 || y<0 || x>=n || y>= m || maze[x][y] != 1) {
            return ;
        } else{
            //将走过的点添加到list链表中记录
            list.add("[" + x + "," + y + "]");
            //走过的点置0，防止回踩此点
            maze[x][y] = 0;
            //如果走到了最中的终点，首先判断是否为最短路径（也就是消耗能量最少的路线）
            // 如果是则将list数据copy到listCopy中去，然后重新返回之前的点进行递归，找出别的可以通向终点的路线
            // 然后将flag置为1
            if (x == 0 && y == m -1 && energy >= 0) {
                if(energy > maxRemainEnergy) {
                    maxRemainEnergy = energy;
                    Copy(list,listCopy);
                }
                maze[x][y] = 1;
                list.removeLast();
                flag = true;
                return;
            }
            //首先选择向右移动
            optimalPath(x, y + 1, energy - 1);
            //如果到达了最后一列，则不进行向下移动，最后一行 向下移动的话肯定会有比他更简单的路径
            if (y != m - 1) {
                optimalPath(x + 1, y, energy);
            }
            //然后判断能否向上移动
            optimalPath(x - 1, y, energy - 3);
            //不需要向左移动，如果向左那肯定不会是最简单的走法
            //将节点置1，继续返回完成递归
            maze[x][y] = 1;
            list.removeLast();
        }
    }

    //链表的复制
    private static void Copy(LinkedList<String> list, LinkedList<String> listCopy) {
        listCopy.clear();
        for(String l : list) {
            listCopy.add(l);
        }
    }

    //打印路线
    private static void printPoint(int[][] maze) {
        for(int i = 0; i < listCopy.size(); i++) {
            System.out.print(listCopy.get(i));
            if (i != listCopy.size() - 1) {
                System.out.print(",");
            }
        }
    }
}

import java.util.*;
public class Main{
    public static class Point{
        int x;
        int y;
        Point(int x,int y){
            this.x = x;
            this.y = y;
        }
        public void printPoint(){
            System.out.print("["+this.x+","+this.y+"]");
        }
    }
    static ArrayList<Point> path = new ArrayList<Point>();
    static int max = -1;
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt(),m = s.nextInt(),p = s.nextInt();
        int[][] a = new int[n][m];
        int i,j;
        for (i = 0;i < n;i++)
            for (j = 0;j < m;j++)
                a[i][j] = s.nextInt();
        ArrayList<Point> list = new ArrayList<Point>();
        nextStep(a,0,0,p,list);
        if (max >= 0 && !path.isEmpty()){
            for (Point temp:path){
                temp.printPoint();
                System.out.print(",");
            }
            new Point(0,m-1).printPoint();
        }else System.out.print("Can not escape!");
    }
    public static void nextStep(int[][] a,int x,int y,int p, ArrayList<Point> list){
        int n = a.length,m = a[0].length;
        if(x == 0 && y == m-1 && p >= 0 && p >= max){
            path.clear();
            path.addAll(list);
            max = p;
            return ;
        }else if (x >= 0 && x < n && y >= 0 && y < m && p > 0 && a[x][y] == 1){
            Point temp = new Point(x,y);
            list.add(temp);
            a[x][y] = 0;
            nextStep(a,x,y+1,p-1,list);
            nextStep(a,x-1,y,p-3,list);
            nextStep(a,x+1,y,p,list);
            nextStep(a,x,y-1,p-1,list);
            list.remove(list.size()-1);
            a[x][y] = 1;
        }else return ;
    }
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int max=-1;
    static ArrayList<String> resList;
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int p=scanner.nextInt();
        int[][] d=new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                d[i][j]=scanner.nextInt();
            }
        }
        dfs(n, m, 0, 0, p, new ArrayList<>(), d);
        if(resList!=null) {
            for(int i=0;i<resList.size();i++) {
                System.out.print(resList.get(i)+",");
            }
            System.out.println("[0,"+(m-1)+"]");
        }else {
            System.out.println("Can not escape!");
        }
    }
    static void dfs(int n,int m,int i,int j,int p,ArrayList<String> list,int[][] d) {
        if(i<0||j<0||i>=n||j>=m||p<0||d[i][j]!=1)return;
        if(i==0&&j==m-1) {
            if(p>max)resList=(ArrayList<String>) list.clone();
        }else {
                list.add("["+i+","+j+"]");
                d[i][j]=0;
                dfs(n, m, i, j-1, p-1, list,d);
                dfs(n, m, i, j+1, p-1, list,d);
                dfs(n, m, i+1, j, p-3, list,d);
                dfs(n, m, i-1, j, p, list,d);
                list.remove(list.size()-1);
            }
        }
}

看评论好多人都是用的DFS，毕竟因为增加了体力限制，所以深度不会太深。其实这道题BFS也可以做，只是需要尽可能判断不走回头路。我的做法是采用了内部类，重写了hashCode()和equals()，采用一个set来存储访问过的节点，从而避免走回头路。

// 节点类，存储当前位置，及父节点和体力
static class Node{
        private int x, y;
        private Node parent;
        private int left;

        public Node(int x,int y, int l, Node p){
            this.x = x;
            this.y = y;
            this.left = l;
            this.parent = p;
        }

        @Override
        public String toString() {
            return String.format("[%d,%d]", x, y);
        }

        @Override
        public int hashCode() {
            return x*10+y;
        }

        @Override
        public boolean equals(Object obj) {
            Node temp = (Node) obj;
            return x == temp.x && y == temp.y;
        }
    }

    private static void findPath(int[][] map, int hp){
        List<Node> list = new ArrayList<>();
        list.add(new Node(0, 0, hp, null));
        // 存储所有访问过的节点
        Set<Node> set = new HashSet<>();
        while(!list.isEmpty()){
            List<Node> next = new ArrayList<>();
            for(Node pos: list){
            // 下一步能到达的节点                
            if(pos.y+1<map[0].length && map[pos.x][pos.y+1] == 1 && pos.left >= 1){
                    next.add(new Node(pos.x, pos.y+1, pos.left-1, pos));
                }
                if(pos.y-1>=0 && map[pos.x][pos.y-1] == 1 && pos.left >= 1)
                    next.add(new Node(pos.x, pos.y-1, pos.left-1, pos));
                if(pos.x+1<map.length && map[pos.x+1][pos.y] == 1)
                    next.add(new Node(pos.x+1, pos.y, pos.left, pos));
                if(pos.x-1>=0 && map[pos.x-1][pos.y] == 1 && pos.left>=3)
                    next.add(new Node(pos.x-1, pos.y, pos.left-3, pos));
            }
            List<Node> tl = new ArrayList<>();
            for(Node node : next){
                // 如果节点已经到达过了，就没必要重新走了
                if(set.contains(node))
                    continue;
                else{
                    tl.add(node);
                    set.add(node);
                    // 如果已经达到目标节点，采用一个栈输出
                    if(node.x == 0 && node.y == map[0].length-1){
                        Node temp = node;
                        Stack<Node> stack = new Stack<>();
                        while(temp!=null){
                            stack.push(temp);
                            temp = temp.parent;
                        }
                        StringBuilder sb = new StringBuilder();
                        while(!stack.isEmpty()){
                            sb.append(stack.pop()).append(',');
                        }
                        sb.deleteCharAt(sb.length()-1);
                        System.out.println(sb);
                        return;
                    }
                }
            }
            list = tl;
        }
        // 所有能到达的节点都到达了还是没有目标节点
        // 输出不可达
        System.out.println("Can not escape!");
    }

BFS用于求最短路问题，存储上一跳节点以及vis，和最小值，故用了5个空来存储属性
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {     static int[][][] map;     public static void main(String[] args) throws IOException {         BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));         String[] s = bf.readLine().split(" ");         int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]), p = Integer.parseInt(s[2]);         map = new int[n][m][5];         for(int i = 0; i < n; i++){             s = bf.readLine().split(" ");             for(int j = 0; j < m; j++){                 map[i][j][0] = Integer.parseInt(s[j]);                 map[i][j][1] = Integer.MAX_VALUE;             }         }         LinkedList<frogPoint> q = new LinkedList<>();         q.add(new frogPoint(0, 0, 0));         int[] dx = {0,0,1,-1},dy = {1,-1,0,0};         map[0][0][1] = 0;         while(!q.isEmpty()){             frogPoint t = q.removeFirst();             int tx = t.x, ty = t.y;             for(int i = 0; i < 4; i++){                 int ttx = tx+dx[i], tty = ty+dy[i];                 if(ok(ttx,tty)){                     int v = 0;                     if(i<=1) v = 1;                     else if(i==2) v = 3;                     v+=t.cost;                     if(map[ttx][tty][1]<=v){                         v = map[ttx][tty][1];                     }else{                         map[ttx][tty][1] = v;                         map[ttx][tty][2] = tx;                         map[ttx][tty][3] = ty;                     }                     q.addLast(new frogPoint(ttx, tty, v));                 }             }         }         if(p<map[0][m-1][1])System.out.println("Can not escape!");         else{             int x = 0,y = m-1;             StringBuilder str = new StringBuilder("[0,"+(m-1)+"]");             while(!(x==0&&y==0)){                 int tx = map[x][y][2];                 y = map[x][y][3];                 x = tx;                 str.insert(0, "["+x+","+y+"],");             }             System.out.println(str.toString());         }     }     private static boolean ok(int x,int y) {         // TODO Auto-generated method stub         if(x>=0&&x<map.length&&y>=0&&y<map[0].length&&map[x][y][4]==0){             map[x][y][4] = 1;             return map[x][y][0]==1;         }         return false;     }     private static class frogPoint{         int x,y,cost;         frogPoint(int a, int b, int c){x = a; y = b;cost = c;}     }
}

	

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
//谁能帮我看下，一直80%，谢谢了
public class Main {
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int P = scanner.nextInt();
        int [][]map = new int[n][m];
        for (int i = 0;i < n;i ++) {
            for (int j = 0;j < m;j ++) {
                map[i][j] = scanner.nextInt();
            }
        }
        List <int []> list = new ArrayList<>();
        List <int []> minList = new ArrayList<>();
        int [][]visit = new int[n][m];
        visit[0][0] = 1;
        int []max = new int[1];
        max[0] = Integer.MIN_VALUE;
        list.add(new int[]{0, 0});
        dfs(map, 0, 0, P, visit, list, minList, max);

        if (minList.size() == 0) {
            System.out.print("Can not escape!");
        }

        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < minList.size(); i++) {
                if (i == minList.size() - 1) {
                    sb.append("[" + minList.get(i)[0] + "," + minList.get(i)[1] + "]");
                } else {
                    sb.append("[" + minList.get(i)[0] + "," + minList.get(i)[1] + "]" + ",");
                }
            }
            System.out.println(sb.toString());
        }
    }

    public static void dfs(int [][]map, int x, int y, int rem, int [][]visit, List<int []> road, List<int []> minRoad, int[] max) {
        if (x == 0 && y == map[0].length - 1 && rem >= 0) {
            if (rem > max[0]) {
                max[0] = rem;
                minRoad.clear();
                minRoad.addAll(road);
                return;
            }else {
                return;
            }
        }
        if (rem <= 0) {
            return;
        }



        int [][]way = new int[4][3];
        way[0][0] = 1;
        way[0][1] = 0;
        way[0][2] = 3;

        way[1][0] = -1;
        way[1][1] = 0;
        way[1][2] = 0;

        way[2][0] = 0;
        way[2][1] = 1;
        way[2][2] = 1;

        way[3][0] = 0;
        way[3][1] = -1;
        way[3][2] = 1;

        for (int i = 0;i < way.length;i ++) {
            int x1 = x + way[i][0];
            int y1 = y + way[i][1];
            if (x1 >= map.length || x1 < 0 || y1 >= map[0].length || y1 < 0) {
                continue;
            }
            if (map[x1][y1] == 1 && visit[x1][y1] != 1) {
                visit[x1][y1] = 1;
                road.add(new int[]{x1, y1});
                dfs(map, x1, y1, rem - way[i][2], visit, road, minRoad, max);
                road.remove(road.size() - 1);
                visit[x1][y1] = 0;
            }
        }
    }
}

import java.util.*;
public class Main {
    private static int row, col, energy;
    private static int maxRemain = 0;
    private static int[][] map;
    private static String path = "";
    private static LinkedList<Node> list = new LinkedList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        row = in.nextInt(); col = in.nextInt();
        int energy = in.nextInt();
        map = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++)
                map[i][j] = in.nextInt();
        }
        run(0, 0, energy);
        if (path.length() > 0)
            System.out.println(path);
        else
            System.out.println("Can not escape!");
    }
    private static void run(int i, int j, int energy) {
        if (energy < 0 || i < 0 || i >= row || j < 0 || j >= col || map[i][j] == 0) return;
        list.addLast(new Node(i, j)); map[i][j] = 0;
        if (i == 0 && j == col - 1) {
            //找到一个路径,如果比上一个路径剩余的体力多，则更新路径
            if (energy >= maxRemain) {
                maxRemain = energy;
                updatePath();
            }
        }
        run(i, j+1, energy-1); //水平移动，消耗1点 --> 向右
        run(i-1, j, energy-3); //向上移动，消耗3点
        run(i+1, j, energy); //向下移动，不消耗体力
        run(i, j-1, energy-1); //水平移动，消耗1点 --> 向左
        map[i][j] = 1; list.removeLast(); //回溯

    }
    private static void updatePath() {
        Iterator it = list.iterator();
        StringBuilder sb = new StringBuilder();
        while (it.hasNext()) {
            Node node = (Node) it.next();
            sb.append("["); sb.append(node.getX());
            sb.append(","); sb.append(node.getY()); sb.append("],");
        }
        if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
        path = sb.toString();
    }
}
class Node {
    private int x, y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    int getX() {
        return x;
    }
    int getY() {
        return y;
    }
}

public class Main{

    
    /* 经典的迷宫问题：搜索，同时记录路径即可。
     * 一个疑问：如果去掉程序中的向左走步骤，也是可以AC的，可能测试数据没有以下
     * 情况吧：
     * 1 0 0 0 1
     * 1 1 0 0 1
     * 0 1 0 0 1
     * 1 1 0 0 1
     * 1 0 0 0 1   
     * 1 1 1 1 1
*/
    
    //定义一个结点，表示路径每个点的位置x,y和能量v
    static class Node{

        int x ;
        int y ;
        int v ;
        Node(int x, int y, int v){
            this.x = x;
            this.y = y;
            this.v = v;
        }

    }

    //记录路径，每一格记录前一个走过的路径结点
    private static Node[][] res = new Node[15][15];


    public static void main(String[] args){
        
        //数据输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int p = in.nextInt();
        int maze[][] = new int[n][m];
        for (int i=0; i<n; ++i){
            for (int j=0; j<m; ++j){
                maze[i][j] = in.nextInt();
            }
        }

        //bfs
        boolean isExist = bfs(maze,n,m,p);
        
        if (!isExist){
            System.out.println("Can not escape!");
        }else {
            printPath(res,0,m-1);
            System.out.print("[0," + (m-1) + "]");
        }
    }

    //回溯，打印路径
    public static void printPath(Node[][]res, int n, int m){

        if (n == 0 && m==0 ) return;
        else {
            printPath(res,res[n][m].x,res[n][m].y);
            System.out.print("[" + res[n][m].x  + "," + res[n][m].y +"],");
        }


    }

    public static boolean bfs(int maze[][],int n, int m,int p){

        for (int i=0; i<15;++i){
            for (int j=0; j<15; ++j){
                res[i][j] = new Node(0,0,0);
            }
        }
        boolean visited[][] = new boolean[n][m];
        Deque<Node> q = new LinkedList<>();
        Node node = new Node(0,0,p);
        q.addLast(node);
        while (!q.isEmpty()){
            Node temp = q.pollFirst();
            if (temp.x == 0 && temp.y == m-1 && temp.v >=0 ) {
                    return true;
            }

            // 向下走，消耗体力0
            if (temp.x +1 <n && (maze[temp.x+1][temp.y] == 1 ) && !visited[temp.x+1][temp.y]){

                Node node1 = new Node(0,0,0);
                node1.x = temp.x + 1;
                node1.y = temp.y;
                node1.v = temp.v;

                res[node1.x][node1.y].x = temp.x;
                res[node1.x][node1.y].y = temp.y;
                res[node1.x][node1.y].v = temp.v;

                visited[node1.x][node1.y] = true;
                q.addLast(node1);

            }
            //向右走,消耗体力1
            if ( temp.y+1 < m && (maze[temp.x][temp.y+1] == 1 ) && !visited[temp.x][temp.y+1] && temp.v > 0){
                Node node2 = new Node(0,0,0);
                node2.x = temp.x;
                node2.y = temp.y+1;
                node2.v = temp.v - 1;

                res[node2.x][node2.y].x = temp.x;
                res[node2.x][node2.y].y = temp.y;
                res[node2.x][node2.y].v = temp.v;

                visited[node2.x][node2.y] = true;
                q.addLast(node2);
            }
            //向上走，消耗体力3
            if (temp.x-1 >=0 && (maze[temp.x-1][temp.y] == 1) && !visited[temp.x-1][temp.y] && temp.v >=3){
                Node node3 = new Node(0,0,0);
                node3.x = temp.x-1;
                node3.y = temp.y;
                node3.v = temp.v - 3;

                res[node3.x][node3.y].x = temp.x;
                res[node3.x][node3.y].y = temp.y;
                res[node3.x][node3.y].v = temp.v;

                visited[node3.x][node3.y] = true;
                q.addLast(node3);
            }
            
            //向左走，体力消耗1
            if (temp.y-1 >= 0 && maze[temp.x][temp.y-1] == 1 && !visited[temp.x][temp.y-1] && temp.v>0){
                Node node4 = new Node(0,0,0);
                node4.x = temp.x;
                node4.y = temp.y - 1;
                node4.v = temp.v - 1;

                res[node4.x][node4.y].x = temp.x;
                res[node4.x][node4.y].y = temp.y;
                res[node4.x][node4.y].v = temp.v;

                visited[node4.x][node4.y] = true;
                q.addLast(node4);

            }

        }

        return false;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int p = scanner.nextInt();
            int[][] maze = new int[n][m];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    maze[i][j] = scanner.nextInt();
                }
            }
            Map<String,Integer> map = new HashMap<>();
            Stack<String> stack = new Stack<>();
            Set<String> set = new HashSet<>();
            Object[] res = recursion(map, stack, set, maze, n, m, p,0, 0);
            if (res != null) {
                printStack((Stack<String>)res[1], true);
                System.out.println();
            } else {
                System.out.println("Can not escape!");
            }
        }
    }

    private static Object[] recursion(Map<String, Integer> map, Stack<String> stack, Set<String> set, int[][] maze, int n, int m, int p, int x, int y) {
        String str = genStr(x, y);
        if (p < 0 || set.contains(str)) {
            return null;
        }
        if (map.containsKey(str) && map.get(str) >= p) {
            return null;
        }
        stack.push(str);
        set.add(str);
        if (x == 0 && y == m - 1) {
            return new Object[]{p, stack};
        }
        Object[] temp = new Object[4];
        if (x < n - 1 && maze[x + 1][y] != 0) {
            temp[0] = recursion(map, (Stack<String>)stack.clone(), deepCopy(set), maze, n, m,p , x + 1, y);
        }
        if (y > 0 && maze[x][y - 1] != 0) {
            temp[1] = recursion(map, (Stack<String>)stack.clone(), deepCopy(set), maze, n, m,p - 1, x, y - 1);
        }
        if (y < m - 1 && maze[x][y + 1] != 0) {
            temp[2] = recursion(map, (Stack<String>)stack.clone(), deepCopy(set), maze, n, m,p - 1, x, y + 1);
        }
        if (x > 0 && maze[x - 1][y] != 0) {
            temp[3] = recursion(map, (Stack<String>)stack.clone(), deepCopy(set), maze, n, m,p - 3, x - 1, y);
        }
        int maxP = -1;
        int index = -1;
        for (int i = 0; i < 4; ++i) {
            if (temp[i] != null) {
                Object[] t = (Object[]) temp[i];
                if ((int) t[0] > maxP) {
                    maxP = (int) t[0];
                    index = i;
                }
            }
        }
        if (index == -1) {
            stack.pop();
            set.remove(str);
            map.put(str, p);
            return null;
        } else {
            return (Object[])temp[index];
        }
    }

    private static String genStr(int x, int y) {
        return String.format("[%d,%d]", x, y);
    }

    private static void printStack(Stack<String> stack, boolean lastFlag) {
        String str = stack.pop();
        if (!stack.isEmpty()) {
            printStack(stack, false);
        }
        if (lastFlag) {
            System.out.print(str);
        } else {
            System.out.print(str + ",");
        }
    }

    private static HashSet<String> deepCopy(Set<String> set) {
        HashSet<String> copy = new HashSet<>(set.size());
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            copy.add(iterator.next());
        }
        return copy;
    }
}

package LineCode.Recruit2017.滴滴出行;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 小青蛙有一天不小心落入了一个地下迷宫,
 * 小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。
 * 为了让问题简单,假设这是一个n*m的格子迷宫,
 * 迷宫每个位置为0或者1,0代表这个位置有障碍物,
 * 小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。
 * 小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),
 * 小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,
 * 向上爬一个单位距离需要消耗3个单位的体力值,
 * 向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,
 * 小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
 */
public class 地下迷宫 {

    static int n, m, maxRemainEnergy = 0;
    static int[][] map;
    static boolean flag = false;
    static String path = "";
    static LinkedList<String> linkedlist = new LinkedList<>();

    public static void main(String[] args) {

        //输入
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int P = sc.nextInt();
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        //处理
        runMap(0, 0, P);

        //输出
        if (!flag)
            System.out.println("Can not escape!");
        else
            System.out.println(path);

    }

    public static synchronized void runMap(int x, int y, int energy) {
        if (energy < 0 || x<0 || y<0 || x>=n || y>= m || map[x][y] != 1) return;
        else {
            linkedlist.offer("[" + x + "," + y + "]");
            map[x][y] = 0;
            if (x == 0 && y == m - 1) {
                if (energy >= maxRemainEnergy) {
                    maxRemainEnergy = energy;
                    updatePath();
                }
                map[x][y] = 1; linkedlist.removeLast();
                flag = true; return;
            }
            runMap(x, y+1, energy-1);
            runMap(x+1, y, energy);
            runMap(x-1, y, energy-3);
            runMap(x, y-1, energy-1);
            map[x][y] = 1;linkedlist.removeLast();
        }
    }

    public static void updatePath() {
        StringBuilder sb = new StringBuilder();
        Iterator<String> iterator = linkedlist.iterator();
        while (iterator.hasNext())
            sb.append(iterator.next() + ",");
        if (sb.length() > 0)
            sb.deleteCharAt(sb.length() - 1);
        path = sb.toString();
    }

}

    }
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
         n=s.nextInt();
         m=s.nextInt();
        int pvalue=s.nextInt();
        int i,j;
        arr=new int[n][m];
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
               arr[i][j]=s.nextInt();
        ArrayList<Point>list=new ArrayList();
       dfs(0,0,0,m-1,pvalue,list);
       if(res.isEmpty()){
        System.out.println("Can not escape!");
           return;
       }
       ArrayList<Point> path=res.lastEntry().getValue();
      
        for(i=0;i<path.size();i++){
            if(i==0)
                System.out.print("["+path.get(i).x+","+path.get(i).y+"]");
            else
                System.out.print(",["+path.get(i).x+","+path.get(i).y+"]");
        }
    }
}