首页 > > 程序设计 > Java技术 >

java练习简单DFS POJ-1979 Red and Black

2020-04-22 16:03:17来源：博客园阅读 ()

java练习简单DFS POJ-1979 Red and Black

题目地址

https://vjudge.net/problem/POJ-1979

题目描述

有一个房间地上方砖只有红、黑两色。

以某一块黑砖作为起点，可以向相邻四块磁砖（上下左右）移动。但是，不踩红砖，只能踩黑砖。

输出最多可以踩多少黑砖。

'.' 黑砖
'#' 红砖
'@'起点（唯一，黑砖）

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

思路

简单dfs，找到起点@，从起点处向四个方向搜索，如果是黑砖则再次dfs。将搜索过的砖更改为红色作为标记，记数++。

代码

 1 import java.util.Scanner;
 2 
 3 
 4 /**
 5  * @author vastian
 6  */
 7 public class Main {
 8 
 9     public static void main(String[] args) {
10 
11         while (true) {
12             col = SC.nextInt();
13             row = SC.nextInt();
14 
15             // 吃掉int后面的换行
16             SC.nextLine();
17             if (col == 0 && row == 0) {
18                 break;
19             }
20 
21             count = 0;
22             // 读入地图
23             inputMap();
24 
25             // 找到起点@
26             findStart();
27 
28             // 从起点开始找黑砖
29             dfs(sx, sy);
30 
31             System.out.println(count);
32         }
33 
34     }
35 
36     /**
37      * DX、DY为四个方向的移动向量 上：(0,-1) 下：(0,1) 左：(-1,0) 右：(1,0)
38      */
39     private static final int[] DX = {0, 0, -1, 1};
40     private static final int[] DY = {-1, 1, 0, 0};
41     private static final Scanner SC = new Scanner(System.in);
42 
43 
44     /**
45      * count 记录黑砖个数
46      * sx, sy 对应起点@的坐标 (sx,sy)
47      * row, rol 对应地图大小 行数，列数
48      * map 存地图信息
49      */
50     private static int count = 0;
51     private static int sx, sy, row, col;
52     private static char[][] map;
53 
54     public static void inputMap() {
55         // 读取地图
56         map = new char[row][];
57         for (int i = 0; i < row; i++) {
58             map[i] = SC.nextLine().toCharArray();
59         }
60     }
61 
62     public static void findStart() {
63         // 遍历地图，找到唯一的起点@的坐标 (sx,sy)
64         for (int i = 0; i < row; i++) {
65             for (int j = 0; j < col; j++) {
66                 if (map[i][j] == '@') {
67                     sx = i;
68                     sy = j;
69                     return;
70                 }
71             }
72         }
73     }
74 
75     public static void dfs(int r, int c) {
76 
77         // 将走过的黑砖标记为红砖
78         map[r][c] = '#';
79         count++;
80         // 遍历DX、DY得到四个方向
81         for (int i = 0; i < 4; i++) {
82             // tr、tc为下一步可能走的地方
83             int tr = r + DX[i];
84             int tc = c + DY[i];
85             // 在地图范围内且是黑砖才能继续走
86             if (0 <= tr && tr < row && 0 <= tc && tc < col && map[tr][tc] == '.') {
87                 dfs(tr, tc);
88             }
89         }
90     }
91 
92
93 
94 }