[洛谷]P1101 单词方阵

题目来源 洛谷

算法标签 DFS

题目简介

思路

八方向DFS 这已经不能算在考回溯了
这道题的思路我一开始就飞了

我以为是任意情况下的点，开始能不能凑成“yizhong”这个连续字符串，
所依在这种思考背景下，我进入了误区，直接以（0，0）为起始点，走到右下最终点，过程中dfs八个偏移量判断是否符合条件。
同时输入时检查所有数列，将非“yizhong”的字符清空为“*”，在后续的dfs中直接返回，做一个合理性支剪。

后来我发现两个最大的误区，也是这个题目最重要的部分
1.我们不用从左上到右下，因为字符串永远是y开头，我们只要从y开始判定即可
2.符合的要求只需要是八个方向上的直线，不可能出现曲折的线条

依据第二条和第一条，我们就可以发现我们只用判定以Y为中心(n-1)X(n-1)的范围上是不是有满足条件的直线即可

现在我们依据这个思路列出可能的示意图
这是以(2,2)为Y点的示意图，我们可以观察中心点与八条线上的点的关系

为了理清位置和偏移量的关系我重置了位置图，并画了偏移量的表

即八条直线上的所有位置都可以通过原坐标点以及偏移量来表示
这个时候我们引入stdStr 即题目中要求比对的字符串 “yizhong”的概念，
如果我们的第U个字符串是对应的第U个stdStr字符的话就继续比对，如果一条线上的n-1个都是，即2完成比对

那么我们怎么完成八个方向上的n-1个字符比对呢？
首先我们线比对偏移量为(-1,1)即左上的位置
我们设定

	1.偏移量（-1,1）是所有偏移量中的第P个，只要我们使用(x+dx[p],y+dy[p])即可表示
	2.我们要比对的字符是总数n-1个字符中的第q个，只要我们使用q就可以表示当前第是第几个，而q在完整的过程当中是循环自增到n-1为止的

这样一来我们可以列出检查偏移量（-1,1）时是否满足条件的情况

那么如何检查八个方向呢？
我们只要再控制一个变量，将方向转移八次，然后重复检查单次的操作即可

我写的代码为了方便，并没有使用递归

AC代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;
char g[N][N];//地图
bool backMap[N][N];//备份地图

int dx[] = { -1,0,1,1,1,0,-1,-1 };
int dy[] = { 1,1,1,0,-1,-1,-1,0 };

string stdStr = "yizhong";
int n;

void dfs(int x, int y)
{
	for (int i = 0; i < 8; i++)
	{
		bool checkWay = true;
		for (int j = 1; j < 7; j++)
		{
			int tx = x + dx[i] * j, ty = y + dy[i] * j;//利用乘j来计算相应坐标
			if((unsigned int)tx<n&&(unsigned int) ty<n) ;else {checkWay = false;continue;}//检查边界
			if (g[tx][ty] != stdStr[j]){checkWay = false;break;}//如果不符合目标StdStr 检查下一个方向
		}
		if (!checkWay)continue;

		for (int j = 0; j < 7; j++)//赋值
		{
			int tx = x + dx[i] * j, ty = y + dy[i] * j;
			backMap[tx][ty] = true;
		}
	}
	return;
}
int main()
{
	cin >> n;

	memset(g, '*', sizeof g);//初始化

	for (int i = 0; i < n; i++)cin >> g[i];//string方式读入
    
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (g[i][j] == 'y')
				dfs(i, j);//找到Y点然后开始搜索6X6的范围，是否存在符合条件

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			if (backMap[i][j])//如果满足条件就输出对应字符
				cout << g[i][j];
			else cout << '*';
		cout << endl;
	}

	return 0;
}