第 5 场 算法季度赛
题目：
3.BlueAI【算法赛】 - 蓝桥云课
3. BlueAI【算法赛】
问题描述
2317年，小蓝终于在蓝桥杯国赛中一举夺魁，成为了新一届的国特选手。这次，他不仅赢得了无上的荣耀，更是获得了一个挑战蓝桥杯组委会秘密训练的超级AI——BlueAI的机会。
挑战项目是在一个 N×N 的跳棋棋盘上进行对弈。棋盘上有三种符号：
L: 小蓝的棋子。Q: BlueAI的棋子。.: 空位。
小蓝的棋子可以跳过BlueAI的棋子并吃掉它，但必须满足以下条件：
- 跳跃方向：棋子必须沿着棋盘的四个对角线方向（左上、左下、右上、右下）之一进行跳跃。
- 跳跃条件：沿着选定的对角线方向，与相邻的第一个位置必须是
Q，第二个位置必须是空位。这样，小蓝的棋子就可以跳跃到第二个位置上，并吃掉Q。吃完Q后，原来Q所在的位置将变为空位。 - 多次跳跃：小蓝可以在一次移动中连续吃掉多个BlueAI的棋子。每次跳跃之后，都可以重新选择跳跃方向。也就是说，在吃掉一个
Q后，如果新的位置仍然满足跳跃条件，小蓝可以选择任意一个对角线方向继续跳跃并吃掉下一个Q，以此类推，直到无法继续吃子为止。
现在，给定当前棋盘的状态，你的任务是计算在小蓝的回合中，他一次移动最多可以吃掉多少个BlueAI的棋子。
输入格式
第一行包含一个整数 N (5 ≤ N ≤ 12)，表示棋盘的大小。
接下来的 N 行，每行包含一个长度为 N、仅由 L、Q、. 构成的字符串，表示棋盘的状态。
数据为随机生成，且保证至少存在一个 L。
输出格式
输出一个整数，表示小蓝在一次移动中最多可以吃掉的 Q 的数量。
样例输入
5
.L...
.Q...
.Q...
.Q...
.....样例输出
2思路：
1.对每一个L进行深搜，注意回溯。
2.方向数组是对角线的，第一次一圈确认是否存在q，第二次再次加一次方向数组的值，就是当前L可以跳的点
3.使用全局变量的时候，也要回溯，不然会造成答案总更多。
代码如下：
#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node{
int x;
int y;
};
const int N = 13;
int n;
int cnt;
char map[N][N];
Node list[N*N];//储存l的数组
int ans = -1;
int dx[] = {1,1,-1,-1};
int dy[] = {1,-1,-1,1};
void dfs(int x,int y)
{
for(int k = 0 ; k < 4 ; k++)//先找四个对角线有没有Q
{
int tx = x + dx[k];
int ty = y + dy[k];
if(tx >= 0 && tx < n && ty >= 0 && ty < n)//边界处理
{
if(map[tx][ty] == 'Q' )//找到Q，跳跃
{
int Lx = tx + dx[k];
int Ly = ty + dy[k];
if(Lx >= 0 && Lx < n && Ly >= 0 && Ly < n)//边界处理
{
if(map[Lx][Ly] == '.')
{
cnt++;
map[x][y] = '.';//L的出发点
map[tx][ty] = '.';//Q被吃了
map[Lx][Ly] = 'L';//L的新点
dfs(Lx,Ly);
map[x][y] = 'L';
map[tx][ty] = 'Q';
map[Lx][Ly] = '.';
cnt--;
}
}
}
}
}
ans = max(ans, cnt);
}
int main()
{
int num = 1;
cin >> n;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
cin >> map[i][j];
if(map[i][j] == 'L')
{
list[num].x = i;
list[num].y = j;
num++;
}
}
}
for(int i = 1 ; i < num ; i++)//对每一个L进行深搜
{
cnt = 0;
dfs(list[i].x,list[i].y);
}
cout << ans;
return 0;
}