什么是DFS或BFS这里不详谈，重点介绍并分析几个例子。
题目来源：
DFS
六角填数
1.如图【1.png】所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。
image.png
深度优先搜索的通用解法
http://blog.csdn.net/championlee_cs/article/details/51030336
package Chapter4;
public class SixPoint {
static int[] array=new int[12];
static boolean[] visitArray=new boolean[13];
static boolean isOk(){
int a1=array[0]+array[2]+array[5]+array[7];
int a2=array[0]+array[3]+array[6]+array[10];
int a3=array[7]+array[8]+array[9]+array[10];
int a4=array[1]+array[2]+array[3]+array[4];
int a5=array[1]+array[5]+array[8]+array[11];
int a6=array[4]+array[6]+array[9]+array[11];
if(a1==a2 && a2==a3 && a3==a4 && a4==a5 && a5==a6){
return true;
}else{
return false;
}
}
static void display(){
System.out.println("result:"+array[5]+" and the answer is 10");
}
static void DFS(int order){
if(order>11){
if(isOk()){
display();
}else{
return;
}
}else{
if(order == 0 || order == 11 || order == 1){
DFS(order+1);
return;
}else{
for(int i=1;i<visitArray.length;i++){
if(!visitArray[i]){
array[order]=i;
visitArray[i]=true;
DFS(order+1);
//重点！！需要在此处复原
visitArray[i]=false;
}
}
}
}
}
public static void main(String[] args) {
//从上到下，从左到右，保存这12个数与相应位置
array[0]=1;
array[1]=8;
array[11]=3;
for (int i=0;i<visitArray.length;i++){
visitArray[i]=false;
}
visitArray[1]=true;
visitArray[8]=true;
visitArray[3]=true;
DFS(0);
}
}
八皇后
package Chapter4;
public class EightQueens {
static int N=9;
static int[] row=new int[N];
static int count=0;
static boolean isOk(int a,int b){
if(a==b || row[a]==row[b]){
return false;
}
if(Math.abs(a-b)==Math.abs(row[a]-row[b])){
return false;
}else{
return true;
}
}
static void display(){
System.out.println("the result:"+count);
count++;
for (int i=1;i<N;i++){
for(int j=1;j<N;j++){
if(j==row[i]){
System.out.print(row[i]);
}else{
System.out.print("x");
}
}
System.out.println();
}
}
static void dfs(int rowCount){
if(rowCount>N-1){
display();
return;
}else{
for(int column=1;column<N;column++){
row[rowCount]=column;
boolean flag=true;
for(int rows=1;rows<rowCount;rows++){
if(isOk(rows,rowCount)){
}else{
flag=false;
break;
}
}
if(flag){
dfs(rowCount+1);
row[rowCount]=0;
}
}
}
}
public static void main(String[] args) {
dfs(1);
}
}
result:
image.png
拯救OIBH总部（dfs例子）
背景
OIBH总部突然被水淹没了！现在OIBH需要你的救援……
描述
OIBH被突来的洪水淹没了>.<还好OIBH总部有在某些重要的地方起一些围墙，用号表示，而一个封闭的号区域洪水是进不去的……现在给出OIBH的围墙建设图，问OIBH总部没被淹到的重要区域（由"0"表示）有多少。
格式
输入格式
第一行是两个数，x和y（x,y<=500）
第二行及以下是一个由和0组成的xy的图。
输出格式
输出没被水淹没的OIBH总部的“0”的数量。
样例1
样例输入1
4 5
00000
00*00
0*0*0
00*00
样例输出1
1
样例2
样例输入2
5 5
*****
*0*0*
**0**
*0*0*
*****
样例输出2
5
深搜 灌水
这题 我们就相当于求 路径上不经过 * 能到达边界的点有几个
然后我就可以从边界上开始灌水，染色，遇到 * 就 return
然后就相当于 没有被洪水填到的就是 不会到边界的节点
answer:
package Chapter4;
import java.util.Scanner;
public class SaveOIBH {
static int[] xStep={0,0,-1,1};
static int[] yStep={-1,1,0,0};
static int display(char[][] array){
int count=0;
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if('*'!=array[i][j]){
count++;
}
}
}
return count;
}
static void dfs(int n,int m,int x,int y,char[][] array){
char stopChar='*';
if(n<0 || m<0 || n>x-1 || m>y-1){
return;
}
if(array[n][m]==stopChar){
return;
}
array[n][m]=stopChar;
for(int i=0;i<4;i++){
dfs(n+xStep[i],m+yStep[i],x,y,array);
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int x=in.nextInt();
int y=in.nextInt();
char array[][]=new char[x][y];
for(int i=0;i<x;i++){
String cha=in.next();
array[i]=cha.toCharArray();
}
dfs(0,0,x,y,array);
System.out.println(display(array));
}
}
广度优先搜索
详介
理解广度优先搜索
http://www.cnblogs.com/baiyanhuang/archive/2011/04/17/1999196.html
BFS 广度优先搜索 解析
例题：
poj 4001 抓住那头牛 （广度优先搜索算法）
总时间限制:
2000ms
内存限制:
65536kB
描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
解析：
作为一个只知道bfs大概概念的我，即使是再“水”的题我也无所适从啊！
当然，聪明如我，先把代码打出来，一个个断点打过去就知道最简单的bfs的实现情况啦
code:
package Chapter4;
import java.util.LinkedList;
import java.util.Queue;
public class CatchThatCow {
//定义最大量
static int MAX=100000;
//step[n]的值为n处距离起点的步数，如起点n=5，step[5]=0,则5处离起点5的步数为“走0步就到了”
static int[] step=new int[MAX];
//是否已被访问过，从逻辑上推理，如果这个点访问过，如果继续访问下去一定没有之前访问过再访问下去的路径短
static boolean[] visited=new boolean[MAX];
//记录步骤的队列，在java中简单队列是linkedList，enqueue()对应add(),dequeue对应poll()
static Queue<Integer> bfsTree=new LinkedList<>();
//定义起点N和终点K
static int N=5;
static int K=17;
static int bfs(){
//当前路径的起点
int head=0;
//head接下来可以去的方向
int next=0;
//N为起点，所以n处已被访问
visited[N]=true;
//N离N 0步
step[N]=0;
//入队
bfsTree.add(N);
//bfsTree不为空时循环
while(!bfsTree.isEmpty()){
//得到队列的第一个
head=bfsTree.peek();
//出队
bfsTree.poll();
//根据题意，有三种走向
for(int i=0;i<3;i++) {
if (i == 0) {
next = head - 1;
} else if (i == 1) {
next = head + 1;
} else {
next = head * 2;
}
//超范围了就不管了
if (next < 0 || next >= MAX) {
continue;
}
//被访问了就不管了
if (!visited[next]) {
visited[next] = true;
//next就在head的下一步，所以step++
step[next] = step[head] + 1;
//入队
bfsTree.add(next);
}
//如果下一步是终点，那就输出终点的步数
if (next == K) {
return step[next];
}
}
}
return -1;
}
public static void main(String[] args) {
//输出结果
System.out.println(bfs());
}
}
我想注释还是比较详细的，应该能入个小门了
这个是我理解的原理图
image.png
记录步骤的例题：
这是只得到最短路径长度的代码
package Chapter4;
import java.util.LinkedList;
import java.util.Queue;
class Point{
public int row;
int column;
boolean visited;
int step;
public Point(int x,int y){
this.row=x;
this.column=y;
visited=false;
step=0;
}
}
public class Maze {
static int[][] maze={
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
};
static int[] xStep={-1,1,0,0};
static int[] yStep={0,0,-1,1};
static Queue<Point> bfsTree=new LinkedList<>();
static void bfs(){
Point[][] pointList=new Point[5][5];
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
Point p=new Point(i,j);
pointList[i][j]=p;
}
}
pointList[0][0].visited=true;
bfsTree.add(pointList[0][0]);
while (!bfsTree.isEmpty()){
Point head=bfsTree.poll();
for(int i=0;i<4;i++){
int x=head.row+xStep[i];
int y=head.column+yStep[i];
if(x<0 || y<0 || x>4 || y>4 || maze[x][y]==1){
continue;
}
if(!pointList[x][y].visited){
pointList[x][y].visited=true;
pointList[x][y].step=pointList[head.row][head.column].step+1;
bfsTree.add(pointList[x][y]);
}
if(x==4 && y==4){
display(pointList[4][4]);
return;
}
}
}
}
static void display(Point point){
System.out.println("shortest:"+point.step);
}
public static void main(String[] args) {
bfs();
}
}
接下来我们优化代码，得到最短路径的步骤
package Chapter4;
import java.util.LinkedList;
import java.util.Queue;
class Point{
public int row;
int column;
boolean visited;
int step;
Point lastPoint;
public Point(int x,int y,Point lastPoint){
this.row=x;
this.column=y;
visited=false;
step=0;
this.lastPoint=lastPoint;
}
}
public class Maze {
static int[][] maze={
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
};
static int[] xStep={-1,1,0,0};
static int[] yStep={0,0,-1,1};
static Queue<Point> bfsTree=new LinkedList<>();
static void bfs(){
Point[][] pointList=new Point[5][5];
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
Point p=new Point(i,j,null);
pointList[i][j]=p;
}
}
pointList[0][0].visited=true;
bfsTree.add(pointList[0][0]);
while (!bfsTree.isEmpty()){
Point head=bfsTree.poll();
for(int i=0;i<4;i++){
int x=head.row+xStep[i];
int y=head.column+yStep[i];
if(x<0 || y<0 || x>4 || y>4 || maze[x][y]==1){
continue;
}
if(!pointList[x][y].visited){
pointList[x][y].visited=true;
pointList[x][y].step=pointList[head.row][head.column].step+1;
pointList[x][y].lastPoint=pointList[head.row][head.column];
bfsTree.add(pointList[x][y]);
}
if(x==4 && y==4){
display(pointList);
return;
}
}
}
}
static void display(Point[][] pointList){
Point lastPoint=pointList[4][4];
System.out.println("倒序输出：");
while (lastPoint.lastPoint != null){
System.out.println(lastPoint.row+","+lastPoint.column);
lastPoint=lastPoint.lastPoint;
}
System.out.println("0,0");
}
public static void main(String[] args) {
bfs();
}
}
优化的部分就是在类Point中加入了一个指针，指向上一个点，最后输出，此代码粗糙，是倒序的
