挑战程序竞赛系列（4）：2.1深度优先搜索
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434739
2.1 深度优先搜索
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 1979: Red and Black
水题，直接深度优先搜索即可，代码如下：
public class SolutionDay09_P1979 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int W = in.nextInt();
int H = in.nextInt();
char[][] map = new char[H][W];
if (W == 0 && H == 0)
break;
for (int i = 0; i < H; i++) {
char[] ss = in.next().trim().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = ss[j];
}
}
System.out.println(solve(map));
}
in.close();
}
private static int solve(char[][] map) {
int row = map.length;
int col = map[0].length;
count = 0;
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (map[i][j] == '@'){
dfs(map, i, j);
}
}
}
return count;
}
static int count = 0;
private static void dfs(char[][] map, int i, int j){
map[i][j] = '#';
int row = map.length;
int col = map[0].length;
count ++;
int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
for (int d = 0; d < 4; d++){
int x = i + directions[d][0];
int y = j + directions[d][1];
if (x >= 0 && x < row && y >= 0 && y < col && map[x][y] == '.'){
dfs(map, x, y);
}
}
}
}AOJ 0118: Property Distribution
在H * W的矩形果园里有苹果、梨、蜜柑三种果树， 相邻（上下左右）的同种果树属于同一个区域，给出果园的果树分布，求总共有多少个区域。 （原题的样图中苹果为リ，梨为カ，蜜柑为ミ， 图中共10个区域）undefined 输入： 多组数据，每组数据第一行为两个整数H，W（H <= 100, W <= 100）， H =0 且 W = 0代表输入结束。以下H行W列表示果园的果树分布， 苹果是@，梨是#， 蜜柑是*。undefined 输出： 对于每组数据，输出其区域的个数。
依旧很水，代码如下：
public class SolutionDay09_A0118 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int W = in.nextInt();
int H = in.nextInt();
char[][] map = new char[H][W];
if (W == 0 && H == 0)
break;
for (int i = 0; i < H; i++) {
char[] ss = in.next().trim().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = ss[j];
}
}
System.out.println(solve(map));
}
in.close();
}
private static int solve(char[][] map){
int row = map.length;
int col = map[0].length;
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (map[i][j] != '.'){
count ++;
dfs(map, i, j, map[i][j]);
}
}
}
return count;
}
private static void dfs(char[][] map, int i, int j, char c){
map[i][j] = '.';
int row = map.length;
int col = map[0].length;
int[][] directions = {{-1,0},{1,0},{0,1},{0,-1}};
for (int d = 0; d < 4; d++){
int x = i + directions[d][0];
int y = j + directions[d][1];
if (x >= 0 && x < row && y >= 0 && y < col && map[x][y] == c){
dfs(map, x, y, c);
}
}
}
}AOJ 0033: Ball
有一个形似央视大楼（Orz）的筒，从A口可以放球，放进去的球可通过挡板DE使其掉进B裤管或C裤管里，现有带1-10标号的球按给定顺序从A口放入，问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。undefined 输入： 第一行输入数据组数N。接下来N行为N组具体数据，每组数据中有10个整数，代表球的放入顺序。undefined 输出： 对于每组数据，若策略存在，输出YES；若不存在，输出NOundefined 翻译来自http://blog.csdn.net/synapse7/article/details/14454885
本题有多种解法，dp求最长递减子序列。此处我们用DFS，因为每次最多判断10个球。
思路：
准备两个容器，如果左边容器能放入小球，则继续。否则，尝试放入右边那个容器，如果两个均不能放入小球，那自然而然应该返回”NO”.
鸽巢原理，两个容器中的元素总是满足单调递增，如果出现三个连续的递减元素时，那么两个容器都不能装下第三个元素，因此DFS将直接结束，否则DFS一定能遍历到i>10的情况。代码如下：
public class SolutionDay09_A0033 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++){
for(int j = 1; j <= 10; j++){
ball[j] = in.nextInt();
}
System.out.println(solve(ball));
}
in.close();
}
static int kase;
static int[] ball = new int[15];
static int[] l = new int[15];
static int[] r = new int[15];
private static String solve(int[] ball){
kase = 0;
dfs(1, 1, 1);
return kase == 1 ? "YES" : "NO";
}
private static void dfs(int i, int j, int k){
if (i > 10){ //终止条件
kase = 1;
return;
}
if (kase == 1) return;
if (ball[i] > l[j-1]){ //守卫条件
l[j] = ball[i];
dfs(i+1, j+1, k);
}
if (ball[i] > r[k-1]){ //守卫条件
r[k] = ball[i];
dfs(i+1, j, k+1);
}
}
}POJ 3009: Curling 2.0
扔石头，上下左右四个方向如果某一个方向紧挨着block就不能扔这个方向，否则碰到block停住，block消失，再次四个方向扔。
思路：
DFS穷尽搜索，从起点开始，向四个方向探索，碰到block时，回到上一步，且删除block。如果不幸，在某个方向后达到终点的步数超过了最小规定的步数，那么剪枝，并且在一步步返回时，进行现场还原，重新让删除的block，变回block，且换个方向继续搜索。代码如下：
public class SolutionDay09_P3009 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int w = in.nextInt();
int h = in.nextInt();
row = h;
col = w;
if (w == 0 && h == 0)
break;
int[][] board = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
board[i][j] = in.nextInt();
}
}
System.out.println(solve(board));
}
in.close();
}
static int row, col;
static int sx, sy;
static int min_step;
static int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
private static int solve(int[][] board) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (2 == board[i][j]) {
sx = i;
sy = j;
// 连环跳，好技巧
i = row;
break;
}
}
}
board[sx][sy] = 0;
min_step = 11;
dfs(sx, sy, 0, board);
return min_step > 10 ? -1 : min_step;
}
private static void dfs(int x, int y, int step, int[][] board) {
// 超过最小步数，进行剪枝
if (step >= 10 || step > min_step) {
return;
}
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
// 让石头往固定的方向一直飞
while (nx >= 0 && nx < row && ny >= 0 && ny < col) {
switch (board[nx][ny]) {
case 0: {
// keep go
nx += directions[i][0];
ny += directions[i][1];
}
break;
case 3: {
//到达终点，记录最小步数
if (step + 1 < min_step) {
min_step = step + 1;
}
//重新换个方向
nx = -1;
}
break;
case 1: {
// 撞到了block
if (!(nx - directions[i][0] == x && ny - directions[i][1] == y)) { //起点下一个撞击方向不能紧挨着block
board[nx][ny] = 0;
dfs(nx - directions[i][0], ny - directions[i][1], step + 1, board);
//还原状态
board[nx][ny] = 1;
}
//重新选择一个方向
nx = -1;
}
break;
default:
break;
}
}
}
}
}典型的回溯+剪枝算法，得空得强化整理下，这一章节暂告一段落。