什么是DFS或BFS這里不詳談，重點介紹并分析幾個例子。
題目來源：
DFS
六角填數(shù)
1.如圖【1.png】所示六角形中，填入1~12的數(shù)字。
使得每條直線上的數(shù)字之和都相同。
圖中，已經(jīng)替你填好了3個數(shù)字，請你計算星號位置所代表的數(shù)字是多少？
請通過瀏覽器提交答案，不要填寫多余的內(nèi)容。
image.png
深度優(yōu)先搜索的通用解法
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);
//重點??！需要在此處復(fù)原
visitArray[i]=false;
}
}
}
}
}
public static void main(String[] args) {
//從上到下，從左到右，保存這12個數(shù)與相應(yīng)位置
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總部突然被水淹沒了！現(xiàn)在OIBH需要你的救援……
描述
OIBH被突來的洪水淹沒了>.<還好OIBH總部有在某些重要的地方起一些圍墻，用號表示，而一個封閉的號區(qū)域洪水是進不去的……現(xiàn)在給出OIBH的圍墻建設(shè)圖，問OIBH總部沒被淹到的重要區(qū)域（由"0"表示）有多少。
格式
輸入格式
第一行是兩個數(shù)，x和y（x,y<=500）
第二行及以下是一個由和0組成的xy的圖。
輸出格式
輸出沒被水淹沒的OIBH總部的“0”的數(shù)量。
樣例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
深搜 灌水
這題 我們就相當(dāng)于求 路徑上不經(jīng)過 * 能到達邊界的點有幾個
然后我就可以從邊界上開始灌水，染色，遇到 * 就 return
然后就相當(dāng)于 沒有被洪水填到的就是 不會到邊界的節(jié)點
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));
}
}
廣度優(yōu)先搜索
詳介
理解廣度優(yōu)先搜索
http://www.cnblogs.com/baiyanhuang/archive/2011/04/17/1999196.html
BFS 廣度優(yōu)先搜索 解析
例題：
poj 4001 抓住那頭牛 （廣度優(yōu)先搜索算法）
總時間限制:
2000ms
內(nèi)存限制:
65536kB
描述
農(nóng)夫知道一頭牛的位置，想要抓住它。農(nóng)夫和牛都位于數(shù)軸上，農(nóng)夫起始位于點N(0<=N<=100000)，牛位于點K(0<=K<=100000)。農(nóng)夫有兩種移動方式：
1、從X移動到X-1或X+1，每次移動花費一分鐘
2、從X移動到2*X，每次移動花費一分鐘
假設(shè)牛沒有意識到農(nóng)夫的行動，站在原地不動。農(nóng)夫最少要花多少時間才能抓住牛？
輸入
兩個整數(shù)，N和K
輸出
一個整數(shù)，農(nóng)夫抓到牛所要花費的最小分鐘數(shù)
樣例輸入
5 17
樣例輸出
4
解析：
作為一個只知道bfs大概概念的我，即使是再“水”的題我也無所適從啊！
當(dāng)然，聰明如我，先把代碼打出來，一個個斷點打過去就知道最簡單的bfs的實現(xiàn)情況啦
code:
package Chapter4;
import java.util.LinkedList;
import java.util.Queue;
public class CatchThatCow {
//定義最大量
static int MAX=100000;
//step[n]的值為n處距離起點的步數(shù)，如起點n=5，step[5]=0,則5處離起點5的步數(shù)為“走0步就到了”
static int[] step=new int[MAX];
//是否已被訪問過，從邏輯上推理，如果這個點訪問過，如果繼續(xù)訪問下去一定沒有之前訪問過再訪問下去的路徑短
static boolean[] visited=new boolean[MAX];
//記錄步驟的隊列，在java中簡單隊列是linkedList，enqueue()對應(yīng)add(),dequeue對應(yīng)poll()
static Queue<Integer> bfsTree=new LinkedList<>();
//定義起點N和終點K
static int N=5;
static int K=17;
static int bfs(){
//當(dāng)前路徑的起點
int head=0;
//head接下來可以去的方向
int next=0;
//N為起點，所以n處已被訪問
visited[N]=true;
//N離N 0步
step[N]=0;
//入隊
bfsTree.add(N);
//bfsTree不為空時循環(huán)
while(!bfsTree.isEmpty()){
//得到隊列的第一個
head=bfsTree.peek();
//出隊
bfsTree.poll();
//根據(jù)題意，有三種走向
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);
}
//如果下一步是終點，那就輸出終點的步數(shù)
if (next == K) {
return step[next];
}
}
}
return -1;
}
public static void main(String[] args) {
//輸出結(jié)果
System.out.println(bfs());
}
}
我想注釋還是比較詳細的，應(yīng)該能入個小門了
這個是我理解的原理圖
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();
}
}
接下來我們優(yōu)化代碼，得到最短路徑的步驟
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();
}
}
優(yōu)化的部分就是在類Point中加入了一個指針，指向上一個點，最后輸出，此代碼粗糙，是倒序的
