穷竭搜索

 

暴力枚举

略

 

DFS

深度优先搜索（图中数字代表搜索顺序）

隐含栈，搜索过程中将新出现的待搜索状态压入栈，下一次搜索从栈中取出的状态为刚刚入栈的状态。

 

例题 洛谷P1451

---

题目描述

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 n 和 m。

接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n×m 的矩阵。

输出格式

一行一个整数代表细胞个数。

输入输出样例

输入

4 10
0234500067
1034560500
2045600671
0000000089

输出

4

---

题解

#include<bits/stdc++.h>
using namespace std;

int x[105][105],lx,ly;

int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

void dfs(int a,int b)
{
    x[a][b]=0;
    for(int i=0;i<4;i++)
    {
        int xx=b+dx[i];
        int yy=a+dy[i];
        if(xx>=0&&xx<lx&&yy>=0&&yy<ly&&x[yy][xx]!=0)
        dfs(yy,xx);
    }
}

int main()
{
    cin>>ly>>lx;
    int r=0;
    for(int i=0;i<ly;i++)
    for(int j=0;j<lx;j++)
    scanf("%1d",&x[i][j]);
    for(int i=0;i<ly;i++)
    for(int j=0;j<lx;j++)
    if(x[i][j]!=0)
    {
        r++;
        dfs(i,j);
    }
    cout<<r;
}

 

BFS

宽度优先搜索（数字代表搜索顺序）

运用队列，新出现的待搜索状态放到队尾，等平行的所有搜索状态搜索完后才开始取出下一层的状态。

 

例题 UVA439

---

题目描述

输入8*8的国际象棋棋盘上的2个格子（列：ah，行：18），求马至少多少步从起点（键盘输入的第一个位置）跳到终点（键盘输入的第二个位置）。

输入输出样例

输入

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

输出

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

---

题解

#include<iostream>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;

typedef pair<int,int> p;

int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,2,1,-1,-2};

int bfs(int x1,int y1,int x2,int y2)
{
    int a[8][8];
    queue<p> que;
    que.push(p(x1,y1));
    for(int i=0;i<8;i++)
    for(int j=0;j<8;j++)
    a[i][j]=inf;
    a[x1][y1]=0;
    while(!que.empty())
    {
        p q=que.front();
        que.pop();
        if(q.first==x2&&q.second==y2)
        break;
        for(int i=0;i<8;i++)
        {
            int x=q.first+dx[i];
            int y=q.second+dy[i];
            if(x>7||x<0||y>7||y<0||a[x][y]!=inf)continue;
            else
            {
                a[x][y]=a[q.first][q.second]+1;
                que.push(p(x,y));
            }

        }
    }
    return a[x2][y2];

}

int main()
{
    char k[6];
    while(scanf("%c%c%c%c%c%*c",&k[1],&k[2],&k[3],&k[4],&k[5])==5)
    {
    int a,b,c,d; 
    a=k[1]-'a';
    b=k[2]-'0'-1;
    c=k[4]-'a';
    d=k[5]-'0'-1;
    int x=bfs(a,b,c,d);
    cout<<"To get from "<<k[1]<<k[2]<<" to "<<k[4]<<k[5]<<" takes "<<x<<" knight moves."<<endl;
    }

}

 

 

另：一个关于搜索的网站click here