马的覆盖点 - (dfs走固定步数)

中国象棋是起源于中国的一种棋类游戏，属于二人对抗性游戏的一种，在中国有着悠久的历史。由于用具简单、趣味性强，成为流行极为广泛的棋艺活动。
这天，蒜头君迷上了中国象棋，在和一个大师的巅峰对决中处于下风。他知道自己再走三步，大师就会赢下这一局，于是蒜头君想背水一战。
他想知道这个马走三步之内可以到达的位置，是否有好的对策可以给大师致命一击。现在蒜头君的脑子已经不足以想出马走三步之内能到达的所有位置了，于是他找到作为他好朋友的你来帮忙解决这个问题。
马走动的方法是一直一斜，即先横着或竖着走一格，然后再斜着走一个对角线，俗称“马走日”。马走一次可以达到四周的八个点，故有“八面威风”之说。如果在要去的方向有别的棋子挡住，马就无法走过去，俗称“蹩马腿”。为了简化题目，这里就没有蹩马腿这回事了。

输入格式

第一行输入两个整数 n (1 \le x \le 100),n(1≤x≤100), m(1\le m \le 100)m(1≤m≤100) 代表棋盘行数和列数。
第二行输入两个整数 x (1 \le x \le n),x(1≤x≤n), y (1 \le y \le m)y(1≤y≤m) 代表马的初始位置。

输出格式

输出整个棋盘，’.’代表棋盘上可以落子的点，’#’这个代表马走三步能到达的点。

样例输入

10 9
10 1

样例输出

………
………
………
.#.#…..
#.#.#….
####.#…
#####.#..
##.###…
#.###.#..
######…

#include <iostream>
#include <cstring>
using namespace std;
int n, m, x, y;
char mp[105][105];
int dir[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
void dfs(int x, int y, int step) {
    //这里不需要判重复，1步走到这里和2步走到这里是不同的情况，（因为可以往回走）
    if (step > 3 || x < 1 || x > n || y < 1 || y > m ) { 
        return;
    }
    mp[x][y] = '#';
    for (int i = 0; i < 8; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        dfs(tx, ty, step + 1);
    }
}
int main() {
    cin >> n >> m >> x >> y;
    memset(mp, '.', sizeof(mp));
    dfs(x, y, 0);
    for (int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << mp[i][j];
        }
        cout << endl;
    }
    return 0;
}