欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

寒假每日一题_AcWing1113.红与黑--Java代码

程序员文章站 2022-07-12 22:57:05
...

原题链接

题目描述

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。

输出格式

对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

输入样例:

6 9
. . . . # .
. . . . . #
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
# @ . . . #
. # . . # .
0 0

输出样例

45

解题思路

  • 题目理解
    从唯一指定的黑色瓷砖开始向四周搜索合法的瓷砖,直到遍历完网格中能遍历到的合法瓷砖。给出能合法到达的瓷砖数。说到这即可以用 Flood Fill 算法结合 BFS 或者 DFS 加以求解
  • 图的遍历
    • BFS
      宽搜利用队列,相应的伪代码:

        初始格子入队
         while( 队列非空)
         {  
                   取出队头tp;
                   枚举tp的四个邻格;
                   if 格子是合法的(符合条件的)
                   标记格子是非法的(不符合条件的);
                   当前格子入队;
                   (if 条件亦可以由非法的条件判定)
        }
      
    • DFS
      dfs递归搜索,相应的伪代码:

           传入初始格子坐标;
           标记为非法格子;
           枚举当前格子的四个邻格;
           if 格子是合法的(符合条件的)
           递归访问当前格子的四个邻格
      

Java BFS代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class pair{
	int x,y;
	public pair(int sx,int sy) {
		x = sx;
		y = sy;
	}
}
public class Main {
	
	private static final int N = 25;
	private static char [][] g = new char[N][N];
	private static int n,m;
	
	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
        	 String[] ss = sc.readLine().split(" ");
             n = Integer.valueOf(ss[1]);
             m = Integer.valueOf(ss[0]);
        	if(m==0 || n==0) {
        		break;
        	}
        	int x=0,y=0;
        	
        	for(int i=0;i<n;i++) {
        		String s = sc.readLine();
        		for(int j=0;j<m;j++) {
        			g[i][j] = s.charAt(j);
        			if(g[i][j] == '@') {
        				x = i;
        				y = j;
        			}
        		}
        	}
        	System.out.println(bfs(x,y));
        }
	}
	
	public static int bfs(int sx,int sy) {
		pair p = new pair(sx,sy);
		Queue<pair> q = new LinkedList();
		q.add(p);
		g[sx][sy] = '#';
		int res = 0;
		int dx[] = {-1,0,1,0};
		int dy[] = {0,1,0,-1};
		
		while(!q.isEmpty()) {
			pair tp = q.poll();
			res++;
			for(int i=0;i<4;i++) {
				int x = tp.x+dx[i];
				int y = tp.y+dy[i];
				if(x < 0 || x >= n||y < 0||y >= m|| g[x][y] !='.')
					continue;
				g[x][y] = '#';
				p = new pair(x,y);
				q.add(p);
			}
		}
		return res;
	}
}

Java DFS代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static final int N = 25;
	private static char[][] g = new char[N][N];
	private static int n, m;
	private static int dx[] = { -1, 0, 1, 0 };
	private static int dy[] = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String[] ss = sc.readLine().split(" ");
			n = Integer.valueOf(ss[1]);
			m = Integer.valueOf(ss[0]);
			if (m == 0 || n == 0) {
				break;
			}
			int x = 0, y = 0;

			for (int i = 0; i < n; i++) {
				String s = sc.readLine();
				for (int j = 0; j < m; j++) {
					g[i][j] = s.charAt(j);
					if (g[i][j] == '@') {
						x = i;
						y = j;
					}
				}
			}
			System.out.println(dfs(x, y));
		}
	}

	public static int dfs(int sx, int sy) {
		g[sx][sy] = '#';
		int res = 1;
		for (int i = 0; i < 4; i++) {
			int x = sx + dx[i];
			int y = sy + dy[i];
			if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.')
            res += dfs(x,y);
		}
		return res;
	}
}

总结

  • dfs是图的深度优先搜索,从某个网格格子递归向下搜索,当无法访问时向上回溯,代码确实很简洁,但有时可能会有暴栈的风险。
    bfs是图的宽度优先搜索,即一层一层的搜索,可以求解最短距离问题。

  • 和蛇形矩阵一样,网格题的遍历,填数啥的,可以先预设一个二维数组或者两个一维数组作为偏移量,再通过一重循环改变方向

  • 其次学会java的字符输入流 :BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    String[] ss = sc.readLine().split(" "); //读入的字符串以空格间隔存入字符串数组中

相关标签: DFS BFS dfs java