炸弹人只能在一个位置投放炸弹，炸弹能够同时向“上下左右”四个方向同时射去，但是不能穿墙，求炸弹人能够炸最多敌人的位置
1 import java.util.Iterator; 2 import java.util.LinkedList; 3 import java.util.Scanner; 4 import java.util.TreeSet; 5 import java.util.Scanner; 6 public class One { 7 public static int f(int x,int y,char a[][]){ 8 int num=0; 9 //向上 10 int tx=x,ty=y; 11 while(a[tx][ty]!='#'){ 12 if(a[tx][ty]=='G')num++; 13 tx--; 14 } 15 //向下 16 tx=x; 17 ty=y; 18 while(a[tx][ty]!='#'){ 19 if(a[tx][ty]=='G')num++; 20 tx++; 21 } 22 //向左 23 tx=x; 24 ty=y; 25 while(a[tx][ty]!='#'){ 26 if(a[tx][ty]=='G')num++; 27 ty--; 28 } 29 //向右 30 tx=x; 31 ty=y; 32 while(a[tx][ty]!='#'){ 33 if(a[tx][ty]=='G')num++; 34 ty++; 35 } 36 return num; 37 38 } 39 public static void main(String ags[]){ 40 int n,m,p,q;//n,m为地图行列，p，q为小人游戏开始时的数组位置 41 int d[][]={{0,1},{1,0},{0,-1},{-1,0}};//方向移动控制 42 LinkedList<Note> list=new LinkedList<Note>();//用于存放所有可能达到的点 43 Scanner scanner=new Scanner(System.in); 44 System.out.println("请输入地图行列:"); 45 n=scanner.nextInt(); 46 m=scanner.nextInt(); 47 char a[][]=new char[n][m];//存放地图 48 int book[][]=new int[n][m];//记录某点是否已经走过了 49 System.out.println("请输入地图:"); 50 Scanner in=new Scanner(System.in); 51 for(int i=0;i<n;i++){ 52 for(int j=0;j<m;j++){ 53 a[i][j]=in.next().charAt(0); 54 } 55 System.out.println(""); 56 } 57 System.out.println("请输入小人初始位置:"); 58 p=scanner.nextInt(); 59 q=scanner.nextInt(); 60 61 //开始试探所有可能的点 62 int tx,ty,max=0,m1=0,m2=0;//tx,ty为当前点扩展的数组行列号，max为记录当前最大能消灭敌人的数,m1,m2用来记录能消灭敌人最大数目的位置 63 list.add(new Note(p,q,f(p,q,a)));//将小人初始位置放入链表 64 book[p][q]=1; 65 while(!list.isEmpty()){//如果连比较不为空 66 for(int k=0;k<=3;k++){//四个方向探索 67 tx=list.getFirst().x+d[k][0]; 68 ty=list.getFirst().y+d[k][1]; 69 if(a[tx][ty]=='.'&&book[tx][ty]==0){//如果该点为空的（即小人可以到达的），则将该点加入链表，并且能消灭的敌人数与max比较 70 book[tx][ty]=1; 71 list.add(new Note(tx,ty,f(tx,ty,a))); 72 if(list.getFirst().n>max){ 73 max=list.getFirst().n; 74 m1=list.getFirst().x; 75 m2=list.getFirst().y; 76 } 77 } 78 } 79 list.removeFirst(); 80 } 81 System.out.println("位置"+m1+","+m2+"能消灭最多敌人，数目为:"+max); 82 } 83 } 84 class Note{ 85 int x,y,n; 86 Note(int x,int y,int n){ 87 this.x=x; 88 this.y=y; 89 this.n=n; 90 } 91 }
1 import java.util.Iterator; 2 import java.util.LinkedList; 3 import java.util.Scanner; 4 import java.util.TreeSet; 5 import java.util.Scanner; 6 public class One { 7 public static int m1=0,m2=0,max=0,d[][]={{0,1},{1,0},{0,-1},{-1,0}}; 8 public static void f(int x,int y,char a[][],int book[][]){ 9 int num=0; 10 if(a[x][y]=='.'&&book[x][y]==0){ 11 book[x][y]=1; 12 //计算四个方向能消灭敌人的数目 13 //向上 14 int x1=x,y1=y; 15 while(a[x1][y1]!='#'){ 16 if(a[x1][y1]=='G')num++; 17 x1--; 18 } 19 //向下 20 x1=x; 21 y1=y; 22 while(a[x1][y1]!='#'){ 23 if(a[x1][y1]=='G')num++; 24 x1++; 25 } 26 //向左 27 x1=x; 28 y1=y; 29 while(a[x1][y1]!='#'){ 30 if(a[x1][y1]=='G')num++; 31 y1--; 32 } 33 //向右 34 x1=x; 35 y1=y; 36 while(a[x1][y1]!='#'){ 37 if(a[x1][y1]=='G')num++; 38 y1++; 39 } 40 41 if(num>max){//若该点能消灭敌人的数目比之前最大记录大，交换 42 max=num; 43 m1=x; 44 m2=y; 45 } 46 //扩展 47 for(int k=0;k<=3;k++){ 48 int tx,ty; 49 tx=x+d[k][0]; 50 ty=y+d[k][1]; 51 f(tx,ty,a,book); 52 } 53 } 54 return; 55 } 56 //深度优先炸弹人 57 public static void main(String args[]){ 58 int n,m,p,q; 59 Scanner readInt=new Scanner(System.in); 60 Scanner readString=new Scanner(System.in); 61 System.out.println("请输入地图的行列:"); 62 n=readInt.nextInt(); 63 m=readInt.nextInt(); 64 char a[][]=new char[n][m]; 65 int book[][]=new int[n][m]; 66 System.out.println("请输入地图:"); 67 for(int i=0;i<n;i++){ 68 for(int j=0;j<m;j++){ 69 a[i][j]=readString.next().charAt(0); 70 } 71 System.out.println(""); 72 } 73 System.out.println("输入初始位置:"); 74 p=readInt.nextInt(); 75 q=readInt.nextInt(); 76 77 //深度优先算法 78 f(p,q,a,book); 79 System.out.println("位置"+m1+","+m2+"能消灭最多敌人，数目为:"+max); 80 } 81 }
运行如下图所示：
