P9795题解

· · 题解

P9795 [NERC2018] Easy Chess题解

我们直入主题——

算法

看到题目，我首先能想到的是 DFS（深度优先搜索）。

关于深搜

这是一种对状态空间进行枚举，通过穷举来找到最优解，或者统计合法解的个数的算法，能够用来求解这道题。

思路

具体思路就是对当前棋子可以走的方向和距离进行搜索并保存和更新答案，当步数超过要求时返回，直到搜索到在规定步数内到达目的地时输出答案并结束程序。

AC CODE

#include<bits/stdc++.h>
#define int long long//不开 long long 见祖宗（doge
using namespace std;
int n;
bool mp[10][10];//表示是否访问过
int cnt, step[70][5];//记录答案
bool flag;//标记结束
int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
void dfs(int x, int y) {
    if (x == 8 && y == 8 && cnt == n) {
        for (int i = 1; i <= n; i++) {//输出答案
            char c = 'a' + (char)(step[i][1] - 1);
                //因为答案中我们存储的是整型，所以要转化为相应字符
            cout << c << step[i][2] << " ";
        }
        flag = 1;//标记已经找到答案，也可以使用 exist(0)
        return;
    }
    if (cnt == n) return;//当步数超过时返回
    //这个十分重要，本人因此被卡了十分钟
    for (int i = 1; i <= 4; i++) {//枚举方向
        for (int j = 1; j <= 7; j++) {//枚举移动长度
            int kx = x + dx[i] * j, ky = y + dy[i] * j;
            if (kx > 8 || kx < 1 || ky > 8 || ky < 1) continue;//排除越界情况
            if (mp[kx][ky] == 0) {//没有被访问
                mp[kx][ky] = 1;
                cnt++;
                step[cnt][1] = kx, step[cnt][2] = ky;
                dfs(kx, ky);
                cnt--;
                mp[kx][ky] = 0;
                if (flag == 1) return;//已经找到答案，可以继续返回
            }
        }
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//快读
    cin >> n;
    cout << "a1 ";//先输出第一个位置
    mp[1][1] = 1;//注意预处理第一个位置
    dfs(1, 1);
    return 0;
}