一道困扰了我很久的题 虽然是橙
最开始写的:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr int N = 110;
char map[N][N], ans[N][N];
int n, group;
bool st[N][N];
#define fore(i, a, n) for (int i = a; i <= n; i ++)
struct awa{
int x, y;
}le[N];
const int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[] = {1, 0, -1, 1, -1, 0, 1, -1};
const string str = "0yizhong"; // 记得下表要 -1
void print(char map[][110]){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= n; j ++)
cout << map[i][j];
cout << endl;
}
}
void dfs(int x, int y, int num){ // 在(x, y)搜索 在搜num字母
if (num > 7) return;
for (int i = 0; i < 8; i ++){
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > n || st[xx][yy]) continue;
// 这里我想的是 我只匹配一次 不会再搜第二次同一个字母
if (map[xx][yy] == str[num]){
ans[xx][yy] = str[num];
st[xx][yy] = true;
dfs(xx, yy, num + 1);
st[xx][yy] = false;
}
}
}
int main(){
memset(ans, '*', sizeof ans);
cin >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++){
cin >> map[i][j];
if (map[i][j] == 'y'){
group ++;
le[group].x = i;
le[group].y = j;
}
}
for (int i = 1; i <= group; i ++)
dfs(le[i].x, le[i].y, 1);
print(ans);
}
后来发现 if (map[xx][yy] == str[num])
这一段不对 会导致四周有匹配字母的全部显示出来并且删不掉
直接DFS
相当于就是在 i 的八个相邻方向上都尝试找 z ,找到了就继续
但实际上应该是只在一个方向上找
Talk is easy. Show me your code.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr int N = 11100; // 记得开大点 110过不去的
char map[N][N], ans[N][N];
int n, group;
bool st[N][N];
struct awa{
int x, y;
}le[N];
const int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[] = {1, 0, -1, 1, -1, 0, 1, -1};
const string str = "0yizhong";
void print(char map[][11100]){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= n; j ++)
cout << map[i][j];
cout << endl;
}
}
void dfs(int x, int y, int num){ // 在(x, y)搜索 在搜num字母
if (num > 7) return;
bool temp = 0;
int xx = x, yy = y, k;
for (int i = 0; i < 8; temp = 0, i ++){
x = xx, y = yy;
for (k = 1; k <= 7; ++ k) {// 找到y时 直接枚举八个方向
if (x < 1 || x > n || y < 1 || y > n) break;
if (map[x][y] != str[k]) break;
x += dx[i], y += dy[i];
}
if (k == 8) temp = 1;
if (temp) {
x = xx, y = yy;
for (k = 1; k <= 7; k ++)
ans[x][y] = str[k], x += dx[i], y += dy[i];
}
}
}
int main(){
memset(ans, '*', sizeof ans);
cin >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++){
cin >> map[i][j];
if (map[i][j] == 'y'){
group ++;
le[group].x = i;
le[group].y = j;
}
}
for (int i = 1; i <= group; i ++)
dfs(le[i].x, le[i].y, 1);
print(ans);
}