求助帖:样例过了,但全部WA
  • 板块P1101 单词方阵
  • 楼主ermu99
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/20 14:57
  • 上次更新2023/10/24 00:15:57
查看原帖
求助帖:样例过了,但全部WA
866088
ermu99楼主2023/2/20 14:57
#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef pair<int, int> Pii;

int N;
const char* s = "yizhong";
vector<string> g;//存图
vector<vector<bool>> flag;//是否组成单词
vector<Pii> index;//存下标
int d[8][2] = { {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0} };

void dfs(int m, int n, int k, int di)//di表示当前方向, k表示当前匹配字符
{
	if (s[k] == 0) {
		for (auto& e : index) {
			flag[e.first][e.second] = true;
		}
		return;
	}

	//只有第一个字母需要走八个方向
	if (s[k] == 'y') {
		++k;
		index.push_back({ m, n });
		for (int i = 0; i < 8; ++i) {
			int x = m + d[i][0];
			int y = n + d[i][1];
			if (x >= 0 && y >= 0 && x < N && y < N && g[x][y] == s[k]) {
				index.push_back({ x, y });
				dfs(x, y, k + 1, i);
				index.pop_back();
			}
		}
		index.pop_back();
	}
	else {
		int x = m + d[di][0];
		int y = n + d[di][1];
		if (x >= 0 && y >= 0 && x < N && y < N && g[x][y] == s[k]) {
			index.push_back({ x, y });
			dfs(x, y, k + 1, di);
			index.pop_back();
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	scanf("%d", &N);
	g.resize(N);
	flag.resize(N, vector<bool>(N));
	for (int i = 0; i < N; ++i) {
		cin >> g[i];
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (g[i][j] == 'y') {
				dfs(i, j, 0, 0);
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (flag[i][j]) {
				cout << g[i][j];
			}
			else {
				cout << '*';
			}
		}
		cout << '\n';
	}
	return 0;
}
2023/2/20 14:57
加载中...