三解炸弹人—

原创

枚举解炸弹人—— https://www.cnblogs.com/chiweiming/p/9295262.html

BFS解炸弹人—— https://www.cnblogs.com/chiweiming/p/9338597.html

关于题目的介绍请看枚举解炸弹人。

由于枚举存在漏洞，所以采用BFS或者DFS来解题。

此篇博客用DFS解炸弹人，不管是DFS还是BFS都是通过这两种算法的全局搜索功能搜索出地图上的每个点，

再在搜索的基础上逐个点统计出敌人数即可。

Java

import java.util.*;

public class bomb_Three {

    static int n;    //行

    static int m;    //列

    static int save_x;

    static int save_y;

    static int max=0;

    static int dir[][]= {{0,1},{1,0},{0,-1},{-1,0}};    //右、下、左、上

    static char maze[][];

    static int book[][];    //标记数组

    static void Total(int x,int y) {    //统计灭敌数

        int dx=x;

        int dy=y;

        int num=0;

        while(maze[dx][dy]!='#') {    //右

            if(maze[dx][dy]=='G') {

                num++;

            }

            dy++;

        }

        dx=x;

        dy=y;

        while(maze[dx][dy]!='#') {    //下

            if(maze[dx][dy]=='G') {

                num++;

            }

            dx++;

        }

        dx=x;

        dy=y;

        while(maze[dx][dy]!='#') {    //左

            if(maze[dx][dy]=='G') {

                num++;

            }

            dy--;

        }

        dx=x;

        dy=y;

        while(maze[dx][dy]!='#') {    //上

            if(maze[dx][dy]=='G') {

                num++;

            }

            dx--;

        }

        if(num>max) {

            max=num;

            save_x=x;

            save_y=y;

        }

    }

    static void DFS(int x,int y) {

        for(int i=0;i<4;i++) {

            int dx=x+dir[i][0];

            int dy=y+dir[i][1];

            if(dx<0 || dx>n || dy<0 || dy>m) {

                continue;

            }

            if(maze[dx][dy]!='.' || book[dx][dy]==1) {

                continue;

            }

            Total(dx,dy);

            book[dx][dy]=1;

            DFS(dx,dy);

        //    book[dx][dy]=0;        //这里别回溯

        }

    }

    public static void main(String[] args) {

        Scanner reader=new Scanner(System.in);

        n=reader.nextInt();

        m=reader.nextInt();

        maze=new char[n][m];

        book=new int[n][m];

        int start_x=reader.nextInt();    //炸弹人初始位置

        int start_y=reader.nextInt();

        for(int i=0;i<n;i++) {

            String ss=reader.next();

            maze[i]=ss.toCharArray();

        }

        for(int i=0;i<n;i++) {

            for(int j=0;j<m;j++) {

                book[i][j]=0;

            }

        }

        Total(start_x,start_y);

        DFS(start_x,start_y);

        System.out.println("("+save_x+","+save_y+")"+" "+max);

    }

}

测试用例：

输入：

13 13 3 3

#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############

输出：
(7,11) 10

16:06:30

2018-07-20

巴特西

三解炸弹人——DFS

最新文章

热门文章