POJ 1979 Red and Black 深搜入门

本文主要是介绍POJ 1979 Red and Black 深搜入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给定一个 W*H 的矩形，“.”代表可到达的（黑色瓷片），“#”表示障碍（红色瓷片），某人在一个“@”的起始点，求他所能到达的瓷片有多少个（包括第一所占的瓷片）。

深度优先遍历图 VS 广度优先遍历图

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;public class Main {private static final int MAX_SIZE = 25;private static char tileColor[][] = new char[MAX_SIZE][MAX_SIZE];  // 瓷片的颜色private static boolean pass[][] = new boolean[MAX_SIZE][MAX_SIZE]; // 瓷片是否路过private static int blackNum;    // 能到达的黑色瓷片的数量private static void DFS(int indexI, int indexJ) {// 直到该瓷片都被访问if (pass[indexI][indexJ]) {return;}pass[indexI][indexJ] = true;// 标记已访问瓷片++blackNum;                 // 到达的瓷片加 1 // 向上走if (tileColor[indexI - 1][indexJ] != '#') {DFS(indexI - 1, indexJ);}// 向下走if (tileColor[indexI + 1][indexJ] != '#') {DFS(indexI + 1, indexJ);}// 向左走if (tileColor[indexI][indexJ - 1] != '#') {DFS(indexI, indexJ - 1);}// 向右走if (tileColor[indexI][indexJ + 1] != '#') {DFS(indexI, indexJ + 1);}}public static void main(String[] args) {Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int H;  // 行int W;  // 列int indexC = 0;  // @ 所在的列int indexR = 0;  // @ 所在的行String inputStr;char temp;while (in.hasNext()) {W = in.nextInt();H = in.nextInt();if (H == 0 && W == 0) {break;}// 初始化，因为没墙包着，所以四周需要加墙for (int index = 0; index < MAX_SIZE; index++) {Arrays.fill(tileColor[index], '#');Arrays.fill(pass[index], false);}for (int indexI = 1; indexI <= H; indexI++) {inputStr = in.next();for (int indexJ = 1; indexJ <= W; indexJ++) {temp = inputStr.charAt(indexJ - 1);tileColor[indexI][indexJ] = temp;if (temp == '@') {indexC = indexJ;indexR = indexI;}}}blackNum = 0;  // 初始化DFS(indexR, indexC);out.println(blackNum);}out.flush();}
}

这篇关于POJ 1979 Red and Black 深搜入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---