No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

接下来，我们再看一个问题：

这天，阿Q迷上了中国象棋，在和一个大师的巅峰对决中处于下风。他知道自己再走三步，大师就会赢下这一局，于是阿Q想背水一战。

他想知道这个马走三步之内可以到达的位置，是否有好的对策可以给大师致命一击。现在阿Q的脑子已经不足以想出马走三步之内能到达的所有位置了，于是他找到作为他好朋友的你来帮忙解决这个问题。

输入格式

第一行输入两个整数 $n (1 \le x \le 100), m(1\le m \le 100)$代表棋盘行数和列数。

第二行输入两个整数 $x (1 \le x \le n), y (1 \le y \le m)$代表马的初始位置。

输出格式

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

样例输入

10 9
10 1

样例输出

.........
.........
.........
.#.#.....
#.#.#....
####.#...
#####.#..
##.###...
#.###.#..
######...

讲解

本题我们还是采用dfs的形式来搜索出马能到达的所有位置。不过马的走法不再是之前说的那 44 种，而是日字形的 88 种，而且和之前的题目相比，题目中多加了一个限制条件：只要求标示出马三步之内能到达的点。

在之前的题目当中，由于搜索的过程只和坐标点有关，因此我们只需要用坐标来表示当前状态即可。而在本题中，搜索的过程还和步数有关，因此状态不但要用坐标来表示，还要用步数来表示。简单来说，之前的状态是一个二维的(x, y)，而现在的坐标是(x, y, step)，代表当前搜索到了(x, y)这个点，搜索了step步。

同时，在做这个题的时候还有一些需要注意的小细节。之前我们做迷宫问题的题目时，需要vis数组来判断一个点是否被访问过，现在因为状态不只是现在在哪个点，还有现在走了多少步，因此一步到这个点和两步到这个点对后边的影响是不一样的。

那么我们就不能用之前的vis[x][y]表示这个点访问没访问过了，但是我们可以加一维，变成vis[x][y][step]，记录我们是不是曾经在step步的时候到达了(x, y)这个点，也就是(x, y, step)这个状态是不是被访问过了。

核心代码

int dir[8][2] = { { 2, 1}, {2, -1}, {1, 2}, {1, -2}, {-2, 1}, {-2, -1}, {-1, 2}, {-1, -2}};
void dfs(int x, int y, int step) {
    if (!in(x, y) || step > 3 || vis[x][y][step]) {
        return;
    }
    maze[x][y] = '#';
    vis[x][y][step] = true;
    for (int i = 0; i < 8; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        dfs(tx, ty, step + 1);
    }
}

有时为了代码更加简洁，我们会把判断不合法的状态放到dfs一开始直接return，这样就省去了递归下去的时候的判断，而让不合法的状态下去以后立刻返回来不造成影响。