73 lines
2.1 KiB
C++
73 lines
2.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110;
|
||
char a[N][N];
|
||
int b[N][N];//标识数组中i,j位置的字符是不是需要显示出原本的内容，还是显示星星
|
||
int n;
|
||
|
||
//8个方向
|
||
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; //上下左右
|
||
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1}; //左下，右下，左上，右上
|
||
|
||
//坐标结构体
|
||
struct coord {
|
||
int x, y;
|
||
};
|
||
//目标串
|
||
string s = "yizhong";
|
||
|
||
//这条路线上是怎么记录所有点的
|
||
vector<coord> path;
|
||
|
||
//深搜
|
||
//x,y:坐标
|
||
//step:准备查找第几个字符
|
||
//dir：哪个方向
|
||
void dfs(int x, int y, int step, int dir) {
|
||
//找到所有的字符，表示成功，需要输出
|
||
if (step == s.size()) {
|
||
//修改此路径中所有位置内容需要显示
|
||
for (auto p :path) b[p.x][p.y] = 1;
|
||
return;
|
||
}
|
||
//下一个位置
|
||
int x1 = x + dx[dir], y1 = y + dy[dir];
|
||
//如果不出界，并且下一个字符与目标字符相等
|
||
if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n && s[step] == a[x1][y1]) {
|
||
//加入路径中
|
||
path.push_back({x1, y1});
|
||
//继续探索
|
||
dfs(x1, y1, step + 1, dir);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
cin >> a[i][j];
|
||
//开始深搜
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
if (a[i][j] == s[0]) { //找出所有可能的出发点
|
||
//8个方向都要派出侦查兵
|
||
for (int dir = 0; dir < 8; dir++) {
|
||
//清空路径
|
||
path.clear();
|
||
//放入第一个起始点
|
||
path.push_back({i, j});
|
||
//深度搜索
|
||
dfs(i, j, 1, dir);//以i,j为第一个起点坐标，开始进行探索，这是第一个字符,dir代表方向
|
||
}
|
||
}
|
||
|
||
//输出
|
||
for (int i = 1; i <= n; ++i) {
|
||
for (int j = 1; j <= n; ++j)
|
||
if (b[i][j])cout << a[i][j]; else cout << "*";
|
||
cout << endl;
|
||
}
|
||
return 0;
|
||
} |