搜索 算法

一.深度优先搜索（DFS）

1.基本概念2.基本模板3.问题示例 二.广度优先搜索（BFS）

1.基本概念2.基本模板3.问题示例

  深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。
  沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

递归实现：

void dfs(int k)
{ //k代表递归层数，或者说要填第几个空
  if(所有空已经填完了)
 {   判断最优解/记录答案；
  return; }
 for(枚举这个空能填的选项)
  if(这个选项是合法的)
{  记录下这个空(保存现场)；
  dfs(k+1);
 取消这个空(恢复现场)；
 }
}

四阶数独
1.题目描述

 四阶数独。给出一个4x4的格子，每个格子只能填写1到4的整数，要求每行、每列和四等分更小的正方形部分都刚好由1到4组成。
 给出空白的格子，请问：一共有多少种合法的填写方法？

2.代码

#include 
using namespace std;
#define size 5
int n=4*4,t=0,a[size*size];
int b1[size][5],b2[size][5],b3[size][5];//三个数组分别记录行，列，四小格
void dfs(int x)
{  if(x>n)  //空填满则输出
 { t++;
   for(int i=1;i<=n;i++)
  {cout< 
二.广度优先搜索（BFS） 
1.基本概念 
 广度优先搜索算法是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
  在需要解决连通性，最短路问题时，可以考虑使用广度优先搜索。
 
2.基本模板 
 
 
Q.push(初始状态); //将初始状态入队
 while(!Q.empty())
 { State u=Q.front(); //取出队首
   Q.pop();  //出队
  for(枚举所有可扩展状态)  //找到u的所有可达状态v
  if(是合法的)  //v需要满足某些条件，如未访问过、未在队内等
  Q.push(v);  //入队(同时可能需要维护某些必要信息)
 }
 
 
3.问题示例 
1.问题描述
 
 
 
有一个n x m 的棋盘，在某个点 (x, y)上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
 
 
2.代码
 
#include 
#include 
#include 
#include 
using namespace std;
#define N 310
struct coord
{ int x,y;
};
queue Q;
int a[N][N];
int b[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//马能走的8个方向
int main()
{ int m,n,sx,sy;
  memset(a,-1,sizeof(a));
  cin>>m>>n>>sx>>sy;
  coord t={sx,sy};
  Q.push(t);
  a[sx][sy]=0;
  while(!Q.empty())
  { coord c=Q.front();
    int cx=c.x,cy=c.y;
    Q.pop();
    for(int k=0;k<8;k++)
    {int x=cx+b[k][0],y=cy+b[k][1];
     int d=a[cx][cy];
     if(x<1||x>n||y<1||y>m||a[x][y]!=-1) continue;
     a[x][y]=d+1;
     coord t={x,y};
     Q.push(t);
    }
  }
  for(int i=1;i<=n;i++,puts(" "))
   for(int j=1;j<=m;j++)
    printf("%-5d",a[i][j]);
  return 0;
}