BFS：本质上其实就是一个队列
DFS：本质上其实就是一个递归

油田问题

题目描述
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。

输入
多组输入
输入行数m，以及列数n。
然后输入*和@
1<=n,m<=100

输出
联通块个数
样例输入 Copy

5 5
****@
*@@*@
*@**@
@@@*@
@@**@

样例输出
2

题目分析：这其实就是一个求连通块问题…虽然之前就遇到过类似的板子题目几乎一样的题目但是这个题目在老师讲解之后还是没做出来，总是哪里出了问题，虽然后面看了大佬的题解，但是依然想记录一下这个题目
求连通块的算法有dfs，并查集…
每dfs一次就是一个连通块

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int vis[maxn][maxn];
char c[maxn][maxn];
int n, m;
int dir[8][2] = {
   -1, 0, 1, 0, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1, 1};
void dfs(int x, int y)
{
   
   vis[x][y] = 1;
   for (int i = 0; i < 8; ++i)
   {
   //八个方向遍历
      int xx = x + dir[i][0];
      int yy = y + dir[i][1];
      if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && c[xx][yy] == '@' && !vis[xx][yy])//判断条件
         dfs(xx, yy);
   }
}
int main()
{
   
   while (~scanf("%d %d", &n, &m))
   {
   
      memset(vis, 0, sizeof(vis));
      for (int i = 1; i <= n; ++i)
         scanf("%s", c[i] + 1);//字符串从下标为1开始读入，因为下面的代码都是从1开始判断
      int ans = 0;
      for (int i = 1; i <= n; ++i)
         for (int j = 1; j <= m; ++j)
            if (c[i][j] == '@' && !vis[i][j])
            {
   
               dfs(i, j);//每dfs一次就是一个连通块
               ++ans;
            }
      printf("%d\n", ans);
   }
   return 0;
}

马的遍历问题

题目描述
在5*4的棋盘中，马只能走斜“日”字。马从位置(x, y)处出发，把棋盘的每一格都走一次，且只走一次，请找出所有路径。

输入
x,y，表示马的初始位置。

输出
将每一格都走一次的路径总数，如果不存在该路径则输出“No solution!”。

样例输入
1 1
2 2

样例输出
32
No solution!

ps：马的遍历问题也是一个dfs的题目，只不过这个题目是个死题目，固定的代码
我们从起点开始遍历，一步一步的跳，直到不重复的走完棋盘算一次，每次递归我们都遍历当前点的八个方向，在遍历完之后我们要清除标记方便后序的遍历，防止出现干扰。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int vis[maxn][maxn];
int dir[8][2] = {
   1, 2, -1, 2, 1, -2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};
int ans;
void dfs(int x, int y, int step)
{
   
   if (step == 20) //如果走满了棋盘就加一次
   {
   
      ++ans;
      return;
   }
   for (int i = 0; i < 8; ++i) //八个方向依次遍历
   {
   
      int xx = x + dir[i][0];
      int yy = y + dir[i][1];
      if (xx >= 1 && xx <= 5 && yy >= 1 && yy <= 4 && !vis[xx][yy]) //判断条件
      {
   
         vis[xx][yy] = 1;
         dfs(xx, yy, step + 1); //继续下一次递归
         vis[xx][yy] = 0;       //这个方向递归完之后要重新置0，方便以后的遍历
      }
   }
}
int main()
{
   
   int n, m;
   while (~scanf("%d%d", &n, &m))
   {
   
      vis[n][m] = 1;//标记起点
      ans = 0;
      dfs(n, m, 1);
      vis[n][m] = 0;
      if (ans)
         printf("%d\n", ans);
      else
         printf("No solution!\n");
   }
   return 0;
}

逃离迷宫

题目描述
  给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？
  
输入
  第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
  第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符’.‘表示该位置为空地，字符’*‘表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数，(x1, y1), (x2, y2)表示两个位置，其中x1，x2对应列，y1, y2对应行，保证(x1,y1)位置的字符为’.’，不会出现x1=x2并且y1=y2的情况，这也就是说，这两个位置不会是在同一个点上。
  
输出
  每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。
  
样例输入

2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3

样例输出
no
yes

dfs搜索，因为数据比较大所以需要剪枝
vis[i][j][k]表示走到点（i，j）方向为k的最小步数
读题目要仔细，要多思考，有时候多看一下，多思考一下会更好

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
int dir[4][2] = {
   1, 0, -1, 0, 0, 1, 0, -1};
char s[maxn][maxn];
int x2, y2, ans, n, m, vis[maxn][maxn][4];
void dfs(int x, int y, int dis, int k)
{
   
   if (vis[x][y][dis] >= k) //剪枝
      return;
   vis[x][y][dis] = k;
   if (x == x2 && y == y2) //走到了目的地就返回
   {
   
      ans = 1;
      return;
   }
   for (int i = 0; i < 4; ++i) //四个方向遍历
   {
   
      int xx = x + dir[i][0];
      int yy = y + dir[i][1];
      if (xx < 1 || xx > m || yy < 1 || yy > n || s[xx][yy] == '*') //剪枝
         continue;
      if (i == dis) //方向对了就继续递归
         dfs(xx, yy, i, k);
      else if (k) //能尽量少走弯路就少走
         dfs(xx, yy, i, k - 1);
   }
}
int main()
{
   
   int t, k, x1, y1;
   scanf("%d", &t);
   while (t--)
   {
   
      ans = 0;
      scanf("%d%d", &m, &n);
      for (int i = 1; i <= m; ++i)
         scanf("%s", s[i] + 1);
      scanf("%d%d%d%d%d", &k, &y1, &x1, &y2, &x2); //仔细读题
      for (int i = 0; i < 4; ++i)
      {
   
         memset(vis, -1, sizeof(vis));
         vis[x1][y1][i] = 0; //标记起点
         dfs(x1, y1, i, k);
      }
      printf("%s\n", ans ? "yes" : "no");
   }
   return 0;
}