深信服3-10 笔试第四题 （DFS+回溯）

感谢@offer来啊12138 指正

题目详细：求小王拾取的最大金币数量

地图中1为金币 -1为不可逾越的墙壁 0为空地 小王可以用一次技能消除一个墙壁

思路：

当有两个房间，一个房间的金币比另外一个房间的金币多时 需要回溯金币少的房间 例如图二

public class test {
    static int count = 0;

    static int max = 0;

    static int k = 1;

    //图一
//    static int[][] map = {{0,-1,-1,-1,0}
//                        ,{0,-1,1,-1,0}
//                        ,{0,-1,1,-1,0}
//                        ,{-1,-1,1,1,-1}
//                        ,{-1,-1,1,1,-1}
//                        ,{-1,-1,1,1,-1}
//                        ,{-1,-1,-1,-1,-1}
//            //目标 8
//    };
  //图二
//      static int[][] map = {{0,-1,-1,-1,0}
//                        ,{0,-1,1,-1,0}
//                        ,{0,-1,-1,-1,0}
//                        ,{0,-1,1,1,-1}
//                        ,{0,-1,1,1,-1}
//                        ,{0,-1,1,1,-1}
//                        ,{0,-1,-1,-1,-1}
//            //目标 6
//    };

//    //图三
//static int[][] map2 = {{0,-1,-1,-1,0}
//        ,{0,-1,-1,-1,0}
//        ,{0,-1,-1,-1,0}
//        ,{-1,-1,1,1,-1}
//        ,{-1,-1,1,1,-1}
//        ,{-1,-1,1,1,-1}
//        ,{-1,-1,-1,-1,-1}
//        //目标 0
//};
    static int[][] map = {{0,-1,-1}
                            ,{-1,-1,1}};// 0

    //剪枝图
    static boolean[][] vis;

//    static int[][] map = {{1,-1},{-1,1}};
    public static void main(String[] args) {

        vis = new boolean[map.length][map[0].length];
        for(int i = 0;i<map.length;i++){
            Arrays.fill(vis[i],false);
        }

        dfs(0,0);
        System.out.println(max);
    }

    //k为技能次数
    public static void dfs(int x,int y) {

        if(x >= map.length || y >= map[0].length || x < 0 || y < 0 || vis[x][y]){
            return;
        }

        boolean UseK = false;
        if(k == 1 && map[x][y] == -1){
            //尝试消除墙壁
            k--;
            map[x][y] = 0;
            UseK = true;
        }else if(k == 0 && map[x][y] == -1){
            //无法消除
            return;
        }


        boolean isAdd = false;
        if(map[x][y] == 1){
            count++;
            map[x][y] = 0;
            vis[x][y] = true;
            isAdd = true;
        }else if(map[x][y] == 0){
            vis[x][y] = true;
        }

        dfs(x+1,y);
        dfs(x,y+1);
        dfs(x-1,y);
        dfs(x,y-1);

        //回溯
        if(UseK){
            k = 1;
            map[x][y] = -1;
        }

        if(isAdd) {
            map[x][y] = 1;
            vis[x][y] = false;
            max = Math.max(count,max);
            count--;
        }


    }


}