白书《挑战程序设计竞赛》（第2版）搜索

例题，Lake Counting

八连通图，让你求总共有多少个水坑。 思路如下：

从每个水坑开始往八个方向dfs，如果某个方向上是水坑，那么就从它开始dfs，并且把它标记成不是水坑。一直重复，直到图中没有水坑，那么dfs执行的次数就是答案数。

java代码：

import java.util.Scanner; public class Main { static char[][] map; static int cnt = 0, n, m; public static void main(String[] args) { Scanner cin = new Scanner(System.in); n = cin.nextInt(); m = cin.nextInt(); map = new char[n][m]; for (int i = 0; i < n; ++i) { String s = cin.next(); for (int j = 0; j < m; ++j) { map[i][j] = s.charAt(j); } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (map[i][j] == 'W') { solve(i, j); cnt++; } } } System.out.println(cnt); } public static void solve(int x, int y) { for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = dx + x, ny = dy + y; if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 'W') { map[nx][ny] = '.'; solve(nx, ny); } } } } }

bfs- Red and Blank

从一个起点出发，往四个方向走，问可以走到多少个黑点上。 思路如下：

从起点出发，做bfs，能走的点加入到队列中。加点的时候记录下数量，需要防止重复。

java代码

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Point{ int x,y; public Point(int x, int y) { this.x = x; this.y = y; } }; public class Main { static char[][] map; static int cnt = 0, n, m,sx,sy; static int[]dx={1,-1,0,0}; static int[]dy={0,0,1,-1}; public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { m = cin.nextInt(); n = cin.nextInt(); if(n==0 && m==0) break; cnt = 0; map = new char[n][m]; for (int i = 0; i < n; ++i) { String s = cin.next(); for (int j = 0; j < m; ++j) { map[i][j] = s.charAt(j); if(map[i][j]=='@') { sx=i; sy=j; } } } solve(new Point(sx,sy)); System.out.println(cnt+1); } } public static void solve(Point p) { map[p.x][p.y]='#'; Queue<Point>Q=new LinkedList<Point>(); Q.add(p); while(!Q.isEmpty()) { Point u = Q.peek(); Q.poll(); for(int i=0;i<4;++i) { int nx = dx[i]+u.x,ny=dy[i]+u.y; if(nx>=0&&nx<n&&ny>=0&&ny<m&& map[nx][ny]!='#') { cnt++; map[nx][ny]='#'; Q.add(new Point(nx,ny)); } } } } }

dfs-Ball

思路如下：

用两个变量A和B来表示容器两个开口的最上面元素的值，若当前元素$a_i$比A大的话，那么就把$a_i$放到A中，即A=a[i]，比B大的话就放到B。当所有球都放到容器内，那么代表有值。 java代码： import java.util.Scanner; public class Main{ static int[]a; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); while(n-- > 0) { a=new int[10]; for(int i=0;i<10;++i) a[i]=cin.nextInt(); if(solve(0,0,0)) System.out.println("YES"); else System.out.println("NO"); } } public static boolean solve(int i,int A,int B) { if(i==10) return true; if(a[i] > A) { if(solve(i+1,a[i],B)) return true; } if(a[i]>B) { if(solve(i+1,A,a[i])) return true; } return false; } }