题面：

【2阶-14】马的遍历（二）

题目描述

象棋中的马是走 "日" 字型，现在某 $n \times m$ 个点的棋盘上有一个马，且其中一些点上有柱子阻挡，请你依次判断每一个点是否能被马走到。

PS：马走日是先直走一步，再斜走一步，所以注意柱子可能会阻挡马的路线。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行每行 $m$ 个字符，依次表示点的的情况，H 表示马，. 表示空格子，# 表示柱子。

输出格式

$n$ 行，每行 $m$ 个字符表示该格马是否能够走到，其中 1 表示可以走到，0 表示无法走到。

样例 #1

样例输入 #1

3 3
H#.
...
...

样例输出 #1

101
000
010

样例 #2

样例输入 #2

2 3
H..
##.

样例输出 #2

100
001

提示

• 对于 $50\%$ 数据：$1 \leq n,m \leq 10$。
• 对于 $100\%$ 数据：$1 \leq n,m \leq 500$。

我的代码：

#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {1 , 2 , 2 , 1 , 2 , -1 , 1 , -2 , -1 , -2 , -2 , -1 , -2 , 1 , -1 , 2};
int mark[505][505];
char a[505][505] , ans[505][505];
int n , m , x , y;
void dfs(int x , int y){
	ans[x][y] = '1';
	for(int i = 1 ; i <= 8 ; i++){
		int dx = x + d[i][1];
		int dy = y + d[i][2];
		if(i == 1 || i == 8){
			if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && mark[dx][dy] == 0 && a[dx][dy + 1] != '#'){
				mark[dx][dy] = 1;
				dfs(dx , dy);
			}
		}
		else if(i == 2 || i == 3){
			if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && mark[dx][dy] == 0 && a[dx + 1][dy] != '#'){
				mark[dx][dy] = 1;
				dfs(dx , dy);
			}
		}
		else if(i == 5 || i == 4){
			if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && mark[dx][dy] == 0 && a[dx][dy - 1] != '#'){
				mark[dx][dy] = 1;
				dfs(dx , dy);
			}
		}
		else if(i == 7 || i == 6){
			if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && mark[dx][dy] == 0 && a[dx - 1][dy] != '#'){
				mark[dx][dy] = 1;
				dfs(dx , dy);
			}
		}
	}
}
int main() {
	cin >> n >> m;
	memset(ans , 48 , sizeof ans);
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= n ; j++){
			cin >> a[i][j];
			if(a[i][j] == 'H'){
				x = i;
				y = j;
				a[i][j] = '1';
			}
		}
	}
	dfs(x , y);
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++) cout << ans[i][j];
		cout << endl;
	}	
	return 0;
}