啊哈！算法笔记（JAVA版）

程序员文章站 2022-06-11 11:11:03

...

啊哈！算法

1、排序

1.1、桶排序

package 第一章;

import java.util.Scanner;

public class _1_1 {

	
	//算是 桶排序 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int []book = new int[1001];
		for(int i = 0 ; i <= 1000 ; i++){
			book[i] = 0; //初始化为0
		}
		
		
		int t=0 ;
		int n = sc.nextInt(); //输入一个数n ,要输入n个数
		for(int i = 1 ; i <= n ; i++){ //读入，并进行桶排序
			t = sc.nextInt(); //把每一个数读到变量 t 中
			book[t]++; //进行计数，对编号为t 的桶放一个小旗子
		}
		
		for(int i = 1000 ;  i >= 0 ; i--){ //依次判断编号 1000~0的桶
			for(int j = 1 ; j <= book[i] ; j++){ //出现了几次就将桶的编号打印几次
				System.out.printf("%d " , i);
			}
		}
		
		
	}

}

1.2、冒泡排序

package 第一章;

import java.util.Scanner;

public class _1_1 {

	
	//算是 桶排序 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int []book = new int[1001];
		for(int i = 0 ; i <= 1000 ; i++){
			book[i] = 0; //初始化为0
		}
		
		
		int t=0 ;
		int n = sc.nextInt(); //输入一个数n ,要输入n个数
		for(int i = 1 ; i <= n ; i++){ //读入，并进行桶排序
			t = sc.nextInt(); //把每一个数读到变量 t 中
			book[t]++; //进行计数，对编号为t 的桶放一个小旗子
		}
		
		for(int i = 1000 ;  i >= 0 ; i--){ //依次判断编号 1000~0的桶
			for(int j = 1 ; j <= book[i] ; j++){ //出现了几次就将桶的编号打印几次
				System.out.printf("%d " , i);
			}
		}
		
		
	}

}

1.3、快速排序

package 第一章;

import java.util.Scanner;

public class _1_3快速排序 {
	
	static int [] a = new int[101];
	static int n ;
	public static void main(String[] arg){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i = 1 ; i <= n ; i++){
			a[i] = sc.nextInt();
		}
		
		quicksort(1 ,n); //快速排序调用
		
		for(int i = 1 ; i <= n ; i++){
			System.out.printf("%d ", a[i]);
		}
	}
	
	private static void quicksort(int left , int right){
		
		if(left > right){
			return ;
		}
		
		int temp = a[left]; //temp中存的就是基准数
		int i = left;
		int j = right;
		
		while(i != j){
			//顺序很重要，要先从右往左找
			while(a[j] >= temp && i < j){
				j--;
			}
			
			//再从左往右找
			while(a[i] <= temp && i < j){
				i++;
			}
			
			//交换两个数在数组中的位置
			if(i < j){ //当哨兵 i 和哨兵 j 没有相遇时
				int t = a[i];
				a[i] = a[j];
				a[j] = t;
			}
		}
		
		//最终将基准数归位
		a[left] = a[i];
		a[i] = temp;
		
		quicksort(left , i-1); //继续处理左边的，递归的进程
		quicksort(i+1 , right); //继续处理右边，递归 
	}

}

1.4、案例：买书

啊哈！算法笔记（JAVA版）

//方法一

package 第一章;

import java.util.Scanner;

public class _1_4去重加冒泡 {

	static int[] a = new int[101];
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 输入n
		
		for (int i = 1; i <= n; i++) { // 循环读入n个图书的 ISBN号
			a[i] = sc.nextInt();
		}

		// 冒泡排序
		for (int i = 1; i <= n - 1; i++) {
			for (int j = 1; j <= n - i; j++) {
				if (a[j] > a[j + 1]) {
					int t = a[j];
					a[j] = a[j + 1];
					a[j + 1] = t;
				}
			}
		}
		
		System.out.printf("%d ", a[1]); //输出第一个数
		
		for(int i = 2 ; i <= n ; i++){ //从2循环到n
			if(a[i] != a[i-1]) { //如果当前这个数是第一个出现则输出 
				System.out.printf("%d ", a[i]);
			}
		}
	}

}

//方法二

package 第一章;

/*
 * 桶排序是最快的，它的时间复杂度是
O(N+M)；冒泡排序是 O(N  2 )；快速排序是 O(NlogN)。
 */
import java.io.InputStream;
import java.util.Scanner;

public class _1_4桶排序去重 {

	static int[] a = new int[1001];

	public static void main(String[] args) {

		for (int i = 1; i <= 1000; i++) {
			a[i] = 0; // 初始化
		}

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 输入n
		
		for (int i = 1; i <= n; i++) { // 循环读入n个图书的 ISBN号
			int t = sc.nextInt();
			a[t] = 1; // 标记出现过的 ISBN 号
		}

		for (int i = 1; i <= 1000; i++) { // 依次判断 1~1000这个桶
			if (a[i] == 1) { // 如果这个出现过 就打印出来
				System.out.printf("%d ", i);
			}
		}
		
	}

}

3、枚举！很暴力

3.1、坑爹的奥数

**题目：小明在数学课上遇到一道奥数题是这样的， 3 X 6528 = 3 * X 8256 （代表括号要填入的一个数）,在两个括号内填入相同的数字使得等式成立。

package 第三章;

public class _01坑爹的奥数 {

	public static void main(String[] args) {
		for(int i = 1 ; i <= 9 ; i++){
			if((i*10+3)*6528 == (3*10+i)*8256){
				System.out.println(i);
			}
		}
	}

}

3.2、坑爹的奥数升级版

啊哈！算法笔记（JAVA版）

**方法一：**太多了就不写了（哈哈哈哈！）

啊哈！算法笔记（JAVA版）

方法二：

package 第三章;

public class _01_1 {

	public static void main(String[] args) {

		int[] a = new int[10];
		int[] book = new int[10];
		int i;
		int sum;
		int total = 0;
		// 这里用 a[1] - a[9] 来代a,b,c,d,e,f,h,h,i
		for (a[1] = 1; a[1] <= 9; a[1]++) {
			for (a[2] = 1; a[2] <= 9; a[2]++) {
				for (a[3] = 1; a[3] <= 9; a[3]++) {
					for (a[4] = 1; a[4] <= 9; a[4]++) {
						for (a[5] = 1; a[5] <= 9; a[5]++) {
							for (a[6] = 1; a[6] <= 9; a[6]++) {
								for (a[7] = 1; a[7] <= 9; a[7]++) {
									for (a[8] = 1; a[8] <= 9; a[8]++) {
										for (a[9] = 1; a[9] <= 9; a[9]++) {

											for (i = 1; i <= 9; i++) {
												// 初始化book数组
												book[i] = 0;
											}
											for (i = 1; i <= 9; i++) {
												// 如果某个数出现过就标记一下
												book[a[i]] = 1;
											}
											// 统计共出现了多少个不同的数
											sum = 0;
											for (i = 1; i <= 9; i++) {
												sum += book[i];
											}
											// 如果正好出现了9个不同的数，并且满足等式条件，则输出
											if (sum == 9
													&& a[1] * 100 + a[2] * 10 + a[3] 
													+ a[4] * 100+ a[5] * 10 + a[6]
													 == a[7]* 100+ a[8]* 10 + a[9]) {
												total++;
												System.out
														.printf("%d%d%d+%d%d%d=%d%d%d\n",
																a[1], a[2],
																a[3], a[4],
																a[5], a[6],
																a[7], a[8],
																a[9]);
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}

		System.out.println("total=" + total / 2);
	}

}

3.3、火柴棍等式

啊哈！算法笔记（JAVA版）

/*
	测试用例：18
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
一共可以拼出9不同的等式

*/

package 第三章;

import java.util.Scanner;

public class _3_3火柴棍等式 {
	
	public static void main(String[] args) {
		int sum = 0; //用来计数，初始化为0
		
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(); //读入火柴棍的个数 
		
		//开始枚举a和b
		for(int a = 0 ; a <= 1111 ; a++){
			for(int b = 0 ; b <= 1111 ; b++){
				int c = a + b; //计算出c
				
				//fun函数用来计算一个数需要用到多的火柴总数
				/*当a使用的火柴棍数  + b 使用的火柴棍的根数 + c 使用的火柴棍的根数之和
					恰好等于 m-4 时，则成功地找出一组解
				*/
				//m - 4  : -4是因为去掉   + ，- 号 各需要两根
				if(fun(a) + fun(b) + fun(c) == m - 4){
					System.out.printf("%d+%d=%d\n", a,b,c);
					sum++;
				}
			}
		}
		
		System.out.println("一共可以拼出"+sum+"不同的等式");
		
	}
	
	private static int fun(int x){
		int num = 0; //用来计数
		
		//用一个数组来记录 0 - 9 每个数字需要的 火柴棍数
		//6 代表 0 需要 6根来组成
		int []f = {6,2,5,5,4,5,6,3,7,6};
		
		while(x / 10 != 0 ){ //如果x/10的商不等于0，说明这个数至少有两位
			
			//获得x的末尾数字并将此数所需要用到的火柴棍数累加到num中
			num = num + f[x%10];
			
			x = x / 10; //去掉x的末尾数字，例 x的值为 123 则现在x的值为12			
		}
		//最后加上此时x所需用到火柴的概数（此时x一定是一位数）
        //因为最后只剩一位数的时候就会退出上面的循环，所以最后要加上最后一柆数
		num = num + f[x];
		return num; //返回需要火柴的总根数
	}

}

3.4 数的全排列

暴力法

//123的全排列 （多少数就要有多少层循环）
package 第三章;

public class _3_4数的全排列 {


	public static void main(String[] args) {
		for(int a = 1 ; a <= 3 ; a++)
			for(int b = 1 ; b <= 3 ; b++)
				for(int c = 1 ; c <= 3 ; c++){
					if(a != b && a != c && b != c){
						System.out.println(a+""+b+""+c);
					}
				}
	}

}

4、万能的搜索

4.1 、dfs模型

啊哈！算法笔记（JAVA版）

4.2、深度优先

啊哈！算法笔记（JAVA版）

//输入: 0 ~ 9之间的一位数
//输出：倒排
/*

输入：3
输出：123
    132
    213
    231
    312
    321

*/
package 第四章;

import java.util.Scanner;

public class _4_1深度优先搜索 {

	static int[]a = new int[10];
	static int[]book = new int[10];
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); //输入1~9之间的整数
		dfs(1);//首先站在1号小盒子面前
	}
	
	//step表现现在站在第几个盒子面前 
	private static void dfs(int step){
		
		if(step == n + 1){ //如果站在第n+1个盒子面前 ，则表示前n个盒子已经放好扑克牌
			 //输出一种排列（1-n号盒子中的扑克牌编号）
			for(int i = 1 ; i <= n ; i++){
				System.out.printf("%d",a[i]);
			}
			System.out.println();
			return; //返回之前 的一步（最近一次调用dfs函数的地方）
		}
		
		//此时站在第step个盒子面前
		//按照1、2、3…… 的顺序一一尝试
		for(int i = 1 ; i <= n ; i++){
			
			//判断 扑克牌i是否还在手上
			if(book[i] == 0) { //book等于0表示i号在手上
				//开始尝试使用扑克牌
				a[step] = i; //将i号扑克牌放入到第step个盒子中
				book[i] = 1; //将book[i]设为1，表示i号扑克牌已经不在手上
				
				
				//第step个盒子已经放好扑克牌，接下来需要直到下一盒子面前 
				dfs(step + 1); //递归实现
				book[i] = 0 ;//这是一步很重要，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
				
			}
		}
		
	}

}

4.2.1、改进第三章的奥数题

package 第四章;

public class _4_1_3奥数 {

	static int[] a = new int[10];
	static int[] book = new int[10];
	static int total;

	public static void main(String[] args) {
		dfs(1); // 首先站在一个盒子面前

		System.out.println("total=" + total / 2); // 除以2是因为对称相同

	}

	// step 表示现在站在第几个盒子面前
	private static void dfs(int step) {

		if (step == 10) { // 如果到了第10个盒子面前，表示前9个盒子放好了
			// 判断是否满足等式 xxx + xxx = xxx
			if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == 
				a[7] * 100 + a[8] * 10 + a[9]) {
				
				total++; // 满足就加一
				System.out.printf("%d%d%d+%d%d%d=%d%d%d\n", a[1], a[2], a[3],
						a[4], a[5], a[6], a[7], a[8], a[9]);
			}
			return; // 返回之前的一步（最近调用的地方）

		}

		// 按照1、2、3……的顺序一一尝试
		for (int i = 1; i <= 9; i++) {
			// 等于0说明没用过
			if (book[i] == 0) {
				// 开始尝试
				a[step] = i; // 将牌放到第 step个盒子中
				book[i] = 1; // 标志用过了

				// 第step个盒子已经放置好牌，走到下一个盒子面前
				dfs(step + 1); // 递归

				// 重要的一步，要收回,才能进行下一次
				book[i] = 0;
			}
		}
	}
}

4.3、解救小哈（DFS) ---- 迷宫问题

题目

啊哈！算法笔记（JAVA版）

方向

啊哈！算法笔记（JAVA版）

package 第四章;

import java.util.Scanner;

	/*
	 * 输入；
	 *  5 4
		0 0 1 0
		0 0 0 0
		0 0 1 0
		0 1 0 0
		0 0 0 1
		1 1 4 3
		
		1 1:开始位置
		4 3：终点
		输出：
			7
	 */

public class _4_2解救小哈_迷宫问题 {

	static int[][] a = new int[51][51];
	static int[][] book = new int[51][51];
	static int min = 999999;
	static int p ,q; //终点坐标
	static int n , m; //行，列
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); // 行
		m = sc.nextInt(); // 列

		// 读入迷宫
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		// 读入起点和终点坐标
		int startx = sc.nextInt();
		int starty = sc.nextInt();

		p = sc.nextInt();
		q = sc.nextInt();

		// 从起点开始搜索
		book[startx][startx] = 1; // 标记起点已经在路径中，防止后面重复走

		// 第一个参数是起点的x坐标，第二个参数是起点的y 坐标
		// 第三个参数是初始化步数 0

		dfs(startx, starty, 0);

		// 输出最短的步数
		System.out.println(min);

	}

	private static void dfs(int x, int y, int step) {

		/*
		 *  1.1  1.2  1.3
		 *  2.1  2.2  2.3
		 *  3.1  3.2  3.3
		 *  
		 *         x-1,y
		 *  x,y-1   x,y    x,y+1
		 *  	   x+1 , y
		 */
		
		int next[][] = { 
				{ 0, 1 }, // 向右
				{ 1, 0 }, // 向下
				{ 0, -1 }, // 向左
				{ -1, 0 } // 向上
				};
		
		//判断是否到达小哈的位置（终点）
		if(x == p && y == q){
			
			//更新最小值
			if(step < min){
				min = step;
			}
			return; //注意这里一定要返回
		}
		
		//枚举4种走法（上，下，左，右）
		for(int k = 0 ; k <= 3 ; k++){
			
			//计算下一个点的坐标
			int tx = x + next[k][0];
			int ty = y + next[k][1];
			
			//判断是否越界
			if(tx < 1 || tx > n || ty < 1 || ty > m){
				continue;
			}
			
			//判断该点是否为障碍物或者已经在路径中
			if(a[tx][ty] == 0 && book[tx][ty] == 0){
				book[tx][ty] = 1; //标记这个点走过
				
				dfs(tx , ty , step+1); //开始尝试下一个点
				
				book[tx][ty] = 0; //尝试结束，取消这个点的标记
			}
		}
		
	}

}

4.4、BFS 宽度优先搜索–迷宫

啊哈！算法笔记（JAVA版）

package 第四章;

public class _4_3解救小哈_BFS宽度优先搜索 {

	
	/*
	 * 自定义节点，表示地图上的某个点位
	 */
	static class BfsNode{
		//横坐标
		int x;
		
		//纵坐标
		int y;
		
		//父节点在队列中的编号，输出路径时使用
		int f;
		
		//步数
		int s;

	}
	
	/*
	 * 自定义队列，用来记录探索点的步骤
	 */
	static class BfsQueue{
		BfsNode[] data = new BfsNode[2500];
		int head;
		int tail;
		
		public BfsQueue(int head , int tail){
			this.head = head;
			this.tail = tail;
		}
	}
	
	public static void main(String[] args) {
		
		//定义一个表示方向的数组，分别，右，下，左，上
		int[][] next = {
				{0,1},
				{1,0},
				{-1,0},
				{0,-1}
			};
		
		//定义一个桶，用来标记已经路过的点
		int[][] book = new int[50][50];
		
		//初始化地图的矩形大小，初始化地图数据
		int m = 5;
		int n = 4;
		
		int[][] map = new int[50][50];
		
		// 测试用数据
	      map[0][0] = 0;
	      map[0][1] = 0;
	      map[0][2] = 1;
	      map[0][3] = 0;
	      map[1][0] = 0;
	      map[1][1] = 0;
	      map[1][2] = 0;
	      map[1][3] = 0;
	      map[2][0] = 0;
	      map[2][1] = 0;
	      map[2][2] = 1;
	      map[2][3] = 0;
	      map[3][0] = 0;
	      map[3][1] = 1;
	      map[3][2] = 0;
	      map[3][3] = 0;
	      map[4][0] = 0;
	      map[4][1] = 0;
	      map[4][2] = 0;
	      map[4][3] = 1;
		          
		  //初始化入口坐标
	      int startx = 0;
	      int starty = 0;
	      
	      //目标点位
	      int q = 3;
	      int p = 2;
	      
	      //队列初始化
	      BfsQueue queue = new BfsQueue(0,0);
	      
	      //往队列插入迷宫的入口坐标，同时在桶中标记
	      BfsNode starNode = new BfsNode();
	      starNode.x = startx;
	      starNode.y = starty;
	      starNode.f = 0;
	      starNode.s = 0;
	      queue.data[queue.tail] = starNode;
	      queue.tail++;
	      
	      //用于标记是否到达目的点位，1表示到达
	      int flag = 0;
	      
	      //当队列不为空的时候就一直循环
	      while(queue.head < queue.tail){
	    	  
	    	  //下一个点的坐标
	    	  int tx;
	    	  int ty;
	    	  
	    	  //枚举四个方向
	    	  for(int k = 0 ; k < 4 ; k++){
	    		  //计算下一个点的坐标
	    		  tx = queue.data[queue.head].x + next[k][0];
	    		  ty = queue.data[queue.head].y + next[k][1];
	    		  
	    		  //判断下一个点是否越界
	    		  if(tx < 0 || tx >= m || ty < 0 || ty >= n){
	    			  continue;
	    		  }
	    		  
	    		  //判断是否障碍物或者已经走过的点，否则加入到队列 中
	    		  if(map[tx][ty] == 0 && book[tx][ty] == 0){
	    			  //注意：广度优先搜索里每个点只入队一次，和尝试搜索不同，这里不需要book桶清理
	    			  //把走过的点进行标记
	    			  book[tx][ty]  = 1;
	    			  
	    			  //插入新点加到队列中
	    			  BfsNode newNode = new BfsNode();
	    			  newNode.x = tx;
	    			  newNode.y = ty;
	    			  
	    			  //因为当前点是从head处扩展出来的，所以为了记录路径，需要记录上一个点的位置
	    			  newNode.f = queue.head;
	    			  //步数是之前的步数 + 1
	    			  newNode.s = queue.data[queue.head].s + 1;
	    			  queue.data[queue.tail] = newNode;
	    			  queue.tail++;
	    		  }
	    		  
	    		  
	    		  //如果目标点位置到达，则停止扩展，任务结束，退出循环
	    		  if(tx == q && ty == p){
	    			  //标记已结束 
	    			  flag = 1;
	    			  break;
	    		  }
	    	  }
	    	  
	    	  //结束则退出
	    	  if(flag == 1){
	    		  break;
	    	  }
	    	  
	    	  
	    	  //当扩展完一个点之后 ，这个点就没有记录的必要了，进行出队，再对后面的点进行扩展
	    	  
	    	  queue.head++;
	    	  
	    	  
	      }
	      //打印最后一个节点的步数即可，注意tail指针指向最后一个有内容的节点的下一个节点的位置
	      System.out.printf("%d\n",queue.data[queue.tail - 1].s);
	      
		
	}

}

4.5、DFS – 炸弹人问题

啊哈！算法笔记（JAVA版）

package 第四章;

import java.util.Scanner;

// "#"代表墙，"G"代表怪物，"."代表放置炸弹的位置
/*
 * 
 * 输入：
 * 13 13
	#############
	#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#
	#############
	3 3
	
	输出 ：
	Output:
		7 11 10
		
即（7， 11）坐标处可以杀死10个怪物

思路一：遍历图中的每个点，若非墙壁，怪物则计算该点可以杀死多少怪物，循环遍历，
找出最大之（注：但是，不幸的是，这样的的方法对于一些特殊的点不适用，
例如图中的（1，11）点）
 */
public class _4_4DFS_炸弹人问题 {

	static char[][] a = new char[20][21];
	static int book[][] = new int[20][20];
	static int max;
	static int mx, my;
	static int n, m;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// 行，列
		n = sc.nextInt();
		m = sc.nextInt();


		// 读入n行字符
		for (int i = 0; i <= n - 1; i++) {
			String str = sc.next();
			a[i] = str.toCharArray();
		}
		
		//开始的位置
		int startx = sc.nextInt();
		int starty = sc.nextInt();
		
		//从小人所站的位置开始尝试
		book[startx][starty] = 1;
		
		max = getsum(startx , starty); //调用函数
		mx = startx;
		my = starty;
		
		dfs(startx,starty);
		
		System.out.printf("将炸弹放置在(%d,%d),最多可以消灭%d个敌人\n",mx,my,max);
		
		
	}

	private static void dfs(int x , int y){
		
		
		int sum; 
		int tx , ty;
		
		//表示方向数组
		int [][] next ={
				{0,1}, //右
				{1,0}, //下
				{0,-1}, //左
				{-1,0} //上
		};
		
		//计算当前这个点可以消灭的敌人总数
		sum = getsum(x , y);
		
		//更新 max 的值
		if(sum > max ){
			//如果当前的点统计出的所能消灭的数大于max,并用mx 和 my 记录当前的坐标
			max = sum;
			mx = x;
			my = y;
		}
		
		//枚举4个方向
		for(int i = 0 ; i < 4 ; i++){
			//下一个结点的坐标
			tx = x + next[i][0];
			ty = y + next[i][1];
			
			//判断 是否越界
			if(tx < 0 || tx > n -1 || ty < 0 || ty > m -1){
				continue;
			}
			
			//判断是否  围墙或已走过
			if(a[tx][ty] == '.' && book[tx][ty] == 0){
				book[tx][ty] = 1; //标记这个点已走过
				dfs(tx,ty); //开始尝试下一个点
			}
		}
		return;
	}
	
	private static int getsum(int i , int j){
		int x , y;
		int sum = 0; //用来计数（可以消灭的敌人数）
		
		//将坐标i,j复制到两个新变量x,y中，以便之后向上下左右四个方向统计可以消灭的敌人数
		//向上统计可以消灭的敌人数
		x = i;
		y = j;
		while(a[x][y] != '#'){
			if(a[x][y] == 'G'){
				sum++;
			}
			//向上
			x--;
		}
		
		x = i;
		y = j;
		while(a[x][y] != '#'){
			if(a[x][y] == 'G'){
				sum++;
			}
			//向下
			x++;
		}
		
		x = i;
		y = j;
		while(a[x][y] != '#'){
			if(a[x][y] == 'G'){
				sum++;
			}
			//向左
			y--;
		}
		
		x = i;
		y = j;
		while(a[x][y] != '#'){
			if(a[x][y] == 'G'){
				sum++;
			}
			//向右
			y++;
		}
		
		return sum;
	}
}

4.6、BFS – 炸弹人问题

package 第四章;

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


class note {
    int x;
    int y;
    note(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class _4_4BFS_炸弹人问题 {
	static char[][] a = new char[20][20];
    static int[][] book = new int[20][20];
    static Queue<note> queue = new LinkedList<note>();
    static Scanner input = new Scanner(System.in);
    static int n, m;
    static int max=0, mx, my;

    public static void main(String[] args) {
        /**
         *  "#"代表墙，"G"代表怪物，"."代表放置炸弹的位置
         * */
        n = input.nextInt();
        m = input.nextInt();
        for (int l = 0; l < n; l++) {
            String str  = input.next();
            a[l] = str.toCharArray();
        }
        int startX = input.nextInt();
        int startY = input.nextInt();

      //offer() 添加元素
        queue.offer(new note(startX, startY));
        max = getnum(startX, startY);
        mx = startX;
        my = startY;

        bfs();

        System.out.printf("将炸弹放置在(%d,%d),最多可以消灭%d个敌人\n", mx, my, max);

    }

    public static void bfs() {
        int tx, ty, sum;
        int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!queue.isEmpty()) {
            for (int l = 0; l < 4; l++) {
            	
            	// peek() 返回第一个元素
                tx = queue.peek().x + next[l][0];
                ty = queue.peek().y + next[l][1];

                if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) {
                    continue;
                }
                if (a[tx][ty] == '.' && book[tx][ty] == 0) {
                    book[tx][ty] = 1;
                    queue.offer(new note(tx, ty));
                    sum = getnum(tx, ty);
                    if (sum > max) {
                        max = sum;
                        mx = tx;
                        my = ty;
                    }
                }
            }
            queue.remove();
        }
    }
    /**
     * 获取在某点放置炸弹可以杀死的怪物数
     * */
    public static int getnum(int i, int j) {
        int sum, x, y;
        sum = 0;

        x = i;
        y = j;
        while (a[x][y] != '#') {
            if (a[x][y] == 'G') {
                sum++;
            }
            x--;
        }

        x = i;
        y = j;
        while (a[x][y] != '#') {
            if (a[x][y] == 'G') {
                sum++;
            }
            x++;
        }

        x = i;
        y = j;
        while (a[x][y] != '#') {
            if (a[x][y] == 'G') {
                sum++;
            }
            y--;
        }

        x = i;
        y = j;
        while (a[x][y] != '#') {
            if (a[x][y] == 'G') {
                sum++;
            }
            y++;
        }

        return sum;
    }
}

4.7、DFS-宝岛探险

啊哈！算法笔记（JAVA版）

package 第四章;

import java.util.Scanner;
/*
10 10 : 地图大小
6  8 ： 降落位置

10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

 */
public class _4_5宝岛探险 {

	static int[][] a = new int[51][51];
	static int[][] book = new int[51][51];
	static int n, m, sum;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();  //全局变量
		 m = sc.nextInt();
		int startx = sc.nextInt();
		int starty = sc.nextInt();
		
		//读入地图
		for(int i = 1 ;  i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		book[startx][starty] = 1;  //降落位置就开始算 ，标记1
		sum = 1;   //同上
		//从降落的位置开始
		dfs(startx , starty );
		//最后输出岛屿的大小
		System.out.println(sum);
		
		
	}

	private static void dfs(int x, int y ) {
		int k, tx, ty;
	    //定义一个方向数组
	    int next[][] = { { 0, 1 },//向右走
	    { 1, 0 },//向下走
	    { 0, -1 },//向左走
	    { -1, 0 } };//向上走



	    //枚举四个方向
	    for (k = 0; k<4; k++)
	    {
	        //计算下一步的坐标
	        tx = x + next[k][0];
	        ty = y + next[k][1];

	        //判断是否越界
	        if (tx<1 || tx>n || ty<1 || ty>m)
	            continue;

	        //判断是否是陆地
	        if (a[tx][ty]>0 && book[tx][ty] == 0)
	        {
	            sum++;
	            book[tx][ty] = 1; //标记这个点已经走过
	            dfs(tx, ty);//开始尝试下一个点
	        }
	    }
	    return;
		
	}
}

4.7.1、DFS-宝岛探险----染色版本

package 第四章;

import java.util.Scanner;

public class _4_5宝岛探险_染色版 {

	static int[][] a = new int[51][51];
	static int[][] book = new int [51][51];
	static int n , m;
	static int sum;
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();  //地图的大小
		m = sc.nextInt();
		
		int startx = sc.nextInt(); //开始的位置
		int starty = sc.nextInt();
		
		//输入地图
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		book[startx][starty] = 1; //开始位置
		sum = 1;
		dfs (startx , starty, -1); //-1用来染色（标记）
		
		//输出已经染色后的地图
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				System.out.printf("%3d", a[i][j]);
			}
			System.out.println(); 
		}
		
	}
	
	private static void dfs(int x , int y ,int color){
		 int [][] next = {
				 {0,1}, //右
				 {1,0}, //下
				 {0,-1}, //左
				 {-1,0} //上
		 };
		 
		 a[x][y] = color; //对a[x][y]这个格子进行染色 
		 //枚举4个方向
		 for(int k = 0 ; k < 4 ; k++){
			 int tx = x + next[k][0];
			 int ty = y + next[k][1];
			 
			 //判断是否越界
			 if(tx < 1 || tx > n || ty < 1 || ty > m){
				 continue;
			 }
			 
			 //判断是否是陆地    book[tx][ty] == 0 表示 没走过
			 if(a[tx][ty] > 0 && book[tx][ty] == 0){
				 sum++;
				 book[tx][ty] = 1; //标记这个点走过
				 dfs(tx,ty, color);  // 开始尝试下一个点
				 
			 }
			 
		 }
	}

}

/*  输出 ：

  1  2  1  0  0  0  0  0  2  3
  3  0  2  0 -1 -1 -1  0  1  2
  4  0  1  0 -1 -1 -1 -1  0  1
  3  2  0  0  0 -1 -1 -1  0  0
  0  0  0  0  0  0 -1 -1 -1  0
  0 -1 -1 -1  0 -1 -1 -1 -1  0
  0 -1 -1 -1 -1 -1 -1 -1 -1  0
  0  0 -1 -1 -1 -1 -1 -1  0  0
  0  0  0 -1 -1 -1 -1  0  1  2
  0  0  0  0  0  0  0  0  1  0

*/

4.7.2、DFS-宝岛探险 —计算多少个独立小岛版

package 第四章;

import java.util.Scanner;

public class _4_5宝岛探险_查看有多少个独立小岛版 {

	static int [][] a = new int [51][51];
	static int [][] book = new int [51][51];
	static int n , m , sum;
	
	public static void main(String[] args) {
		
		int num = 0;
		
		Scanner sc = new Scanner(System.in);
		
		//地图大小
		n = sc.nextInt();
		m = sc.nextInt();
		 //开始位置
		int startx = sc.nextInt();
		int starty = sc.nextInt();
		
		//输入地图
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		//对每一个大于0的点尝试进行 dfs 染色 
		for(int i = 1; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				if(a[i][j] > 0){
					num--; //小岛需要染的颜色编号
					//每发现一个小岛应染不同的颜色，因此每次要 -1
					book[i][j] = 1;
					dfs(i,j,num);
				}
			}
		}
		
		//输出已经染色后的地图
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				System.out.printf("%3d", a[i][j]);
			}
			System.out.println(); 
		}
	}
	
	private static void dfs(int x, int y , int color){
		//4个方向
		int [][] next = {
				{0,1}, //右
				{1,0}, //下
				{0,-1}, //左
				{-1,0} //上
		};
		
		a[x][y] = color; //对a[x][y]这个格子进行染色 
		
		//枚举4个方向
		for(int k = 0 ; k < 4 ; k++){
			//下一步的坐标
			int tx = x + next[k][0];
			int ty = y + next[k][1];
			
			//判断是否越界
			if(tx < 1 || tx > n || ty < 1 || ty > m){
				continue;
			}
			
			//判断 是否是陆地
			if(a[tx][ty]  > 0 && book[tx][ty] == 0){
				sum++;
				book[tx][ty] = 1; //标记走过
				dfs(tx,ty,color); //开始尝试一个点
			}
		}
		return;
	}

}

/* 输出：
 -1 -1 -1  0  0  0  0  0 -2 -2
 -1  0 -1  0 -3 -3 -3  0 -2 -2
 -1  0 -1  0 -3 -3 -3 -3  0 -2
 -1 -1  0  0  0 -3 -3 -3  0  0
  0  0  0  0  0  0 -3 -3 -3  0
  0 -3 -3 -3  0 -3 -3 -3 -3  0
  0 -3 -3 -3 -3 -3 -3 -3 -3  0
  0  0 -3 -3 -3 -3 -3 -3  0  0
  0  0  0 -3 -3 -3 -3  0 -4 -4
  0  0  0  0  0  0  0  0 -4  0
*/

4.7.3、DFS-宝岛探险 —计算岛屿的相连的总数

package 第四章;

import java.util.Scanner;
/*
10 10 : 地图大小
6 ， 8 ： 降落位置

10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

 */
public class _4_5宝岛探险 {

	static int[][] a = new int[51][51];
	static int[][] book = new int[51][51];
	static int n, m, sum;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();  //全局变量
		 m = sc.nextInt();
		int startx = sc.nextInt();
		int starty = sc.nextInt();
		
		//读入地图
		for(int i = 1 ;  i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		book[startx][starty] = 1;  //降落位置就开始算 ，标记1
		//sum = 1;   //同上
        
		sum = a[startx][starty]; //改了这个
        
		//从降落的位置开始
		dfs(startx , starty );
		//最后输出岛屿的大小
		System.out.println(sum);
		
		
	}

	private static void dfs(int x, int y ) {
		int k, tx, ty;
	    //定义一个方向数组
	    int next[][] = { { 0, 1 },//向右走
	    { 1, 0 },//向下走
	    { 0, -1 },//向左走
	    { -1, 0 } };//向上走



	    //枚举四个方向
	    for (k = 0; k<4; k++)
	    {
	        //计算下一步的坐标
	        tx = x + next[k][0];
	        ty = y + next[k][1];

	        //判断是否越界
	        if (tx<1 || tx>n || ty<1 || ty>m)
	            continue;

	        //判断是否是陆地
	        if (a[tx][ty]>0 && book[tx][ty] == 0)
	        {
	            sum+= a[tx][ty]; //改了这个
	            book[tx][ty] = 1; //标记这个点已经走过
	            dfs(tx, ty);//开始尝试下一个点
	        }
	    }
	    return;
		
	}
}
//输出：124

4.8、水管工游戏（DFS）

啊哈！算法笔记（JAVA版）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Y86Oo8W-1592641609435)(F:\算法笔记\4.8.1.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m85rVvZ9-1592641609436)(F:\算法笔记\4.8.2.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b8A2zLTW-1592641609437)(F:\算法笔记\4.8.3.png)]

package 第四章;

import java.util.Scanner;

/*
 * 
5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4

找到铺设方案

 */
public class _4_6水管工游戏 {

	static int[][] a = new int[51][51];
	static int [][] book = new int[51][51];
	static int n , m ;
	static int flag = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 n = sc.nextInt();
		 m = sc.nextInt();
		//读入游戏地图
		for(int i = 1 ; i <= n ; i++){
			for(int j = 1 ; j <= m ; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		//开始搜索 ，从1，1点开始，进水方向也是1
		dfs(1,1,1);
		
		//判断是否找到铺设方案
		if(flag == 0){
			System.out.println("impossible");
		}else{
			System.out.println("找到铺设方案");
		}
	}
	
	//x和y表示当前处理格子的坐标，front表示进水口方向
	private static void dfs(int x , int y , int front){
		
		//判断是否到达终点，注意这里y的坐标是 m+1 
		//另外判断是否到达终点一定要放在越界判断前面
		if(x == n && y == m+1){
			flag = 1; //找到铺设方案
			return ;
		}
		
		//判断是否越界
		if(x < 1 || x > n || y < 1 || y > m){
			return;
		}
		//判断这个管道是否在路径中已经使用过
		if(book[x][y] == 1){
			return;
		}
		book[x][y] =1; //标记使用当前这个管道
		
		//当前水管是直管的情况
		if(a[x][y] >= 5 && a[x][y] <= 6){
			if(front == 1){ //进水口在  左  边的情况
				dfs(x , y + 1 , 1); //只能使用 5 号这种摆放方式
			}
			if(front == 2){ //进水口在  上 边的
				dfs(x + 1 , y , 2); //只能使用6摆放方式
			}
			if(front == 3){ //进水口在 右  边
				dfs(x , y - 1 , 3); //5号摆放方式
			}
			if(front == 4){ //下边
				dfs(x - 1 , y , 4); //只能使用6号这种摆放方式
			}
		}
		
		//当前水管是弯管的情况
		if(a[x][y] >= 1 && a[x][y] <= 4){
			if(front == 1){ //进水口在左边的情况
				dfs(x + 1 , y , 2); //3号状态
				dfs(x - 1 , y , 4); //4号状态
			}
			if(front == 2){ //进水口在上边
				dfs(x , y + 1 , 1); //1号状态
				dfs(x , y - 1 , 3); //4号状态
			}
			if(front == 3){ //进水口 右边
				dfs(x - 1 , y , 4); //1号状态
				dfs(x + 1 , y , 2); //2号状态
			}
			if(front == 4){ //进水口 下边 
				dfs(x , y + 1 , 1 ); //2号状态
				dfs(x , y - 1 , 3); //3号状态
			}
		}
		
		book[x][y] = 0;  //取消标记
		return;
		
	}
	
	
	
}

啊哈！算法笔记（JAVA版）

啊哈！算法

文章目录

1、排序

1.1、桶排序

1.2、冒泡排序

1.3、快速排序

1.4、案例：买书

3、枚举！很暴力

3.1、坑爹的奥数

3.2、坑爹的奥数升级版

3.3、火柴棍等式

3.4 数的全排列

4、万能的搜索

4.1 、dfs模型

4.2、深度优先

4.2.1、改进第三章的奥数题

4.3、解救小哈（DFS) ---- 迷宫问题

4.4、BFS 宽度优先搜索–迷宫

4.5、DFS – 炸弹人问题

4.6、BFS – 炸弹人问题

4.7、DFS-宝岛探险

4.7.1、DFS-宝岛探险----染色版本

4.7.2、DFS-宝岛探险 —计算多少个独立小岛版

4.7.3、DFS-宝岛探险 —计算岛屿的相连的总数

4.8、水管工游戏（DFS）

Java版超大整数阶乘算法代码详解-10,0000级

Java版超大整数阶乘算法代码详解-10,0000级

使用栈的迷宫算法java版代码

关于JAVA经典算法40题(超实用版)

java版数独游戏核心算法（一）

java实现的海盗算法优化版

K均值聚类算法的Java版实现代码示例

使用栈的迷宫算法java版代码

Java语言Consistent Hash算法学习笔记（代码示例）

Java语言Consistent Hash算法学习笔记（代码示例）

啊哈！算法 笔记（JAVA版）

啊哈！算法

文章目录

1、排序

1.1、桶排序

1.2、冒泡排序

1.3、快速排序

1.4、案例：买书

3、枚举！很暴力

3.1、坑爹的奥数

3.2、坑爹的奥数升级版

3.3、火柴棍等式

3.4 数的全排列

4、万能的搜索

4.1 、dfs模型

4.2、深度优先

4.2.1、改进第三章的奥数题

4.3、解救小哈（DFS) ---- 迷宫问题

4.4、BFS 宽度优先搜索–迷宫

4.5、DFS – 炸弹人问题

4.6、BFS – 炸弹人问题

4.7、DFS-宝岛探险

4.7.1、DFS-宝岛探险----染色版本

4.7.2、DFS-宝岛探险 —计算多少个独立小岛版

4.7.3、DFS-宝岛探险 —计算岛屿的相连的总数

4.8、水管工游戏（DFS）

Java版超大整数阶乘算法代码详解-10,0000级

Java版超大整数阶乘算法代码详解-10,0000级

使用栈的迷宫算法java版代码

关于JAVA经典算法40题(超实用版)

java版数独游戏核心算法（一）

java实现的海盗算法优化版

K均值聚类算法的Java版实现代码示例

使用栈的迷宫算法java版代码

Java语言Consistent Hash算法学习笔记（代码示例）

Java语言Consistent Hash算法学习笔记（代码示例）

啊哈！算法笔记（JAVA版）