洛谷P1101 单词方阵 (C语言 + 详细注释 + 五妙)

//首先声明一下，我的代码大部分是参照洛谷的一位博客：Way_How_Fri3nd。看完后我就觉得写的非常好，由于我不知道怎么转载洛谷的博客，所以干脆自己写一篇CSDN博客，因为写的实在是太好了，我迫不及待地想把其思想和代码分享给大家。

//接下来说一下大体思路，遍历二维数组，每次找到 ‘y’，就从这个点开始，向八个方向搜索，如果哪个方向最终能按顺序到达 ‘g’，说明这条路可行，就把这条路上所经过的字符都标记为1（另开的book数组）。遍历完了，如果一个字符的标记是1，那么输出它本身，标记为0时就输出 ‘*’。思路就介绍到这里，代码里有很多精彩的地方，五妙之处待我一一道来。

下面时是AC的代码：

#include<stdio.h>

int n, book[105][105];          //book数组进行标记
char a[105][105], nextalp[200];              //数组a存储输入数据

int next[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1 , 1} };         //三妙：二维数组next表示向八个方向移动时横纵坐标的变化情况

int dfs(int x, int y, char c, int p) {        //四妙：引用大佬原话：我在哪，我是谁，我要往哪个方向
	if (c == 'g') {                     //如果已经搜到了 ‘g’说明一趟已经结束，并返回1
		book[x][y] = 1;                //标记该点为1
		return 1;
	}
	int tx = x + next[p][0], ty = y + next[p][1];      //tx，ty表示往p方向下一个点的横纵坐标
	if (tx >= 0 && tx < n && ty >= 0 && ty < n && a[tx][ty] == nextalp[c] && dfs(tx, ty, nextalp[c], p)) {       //五妙：第五个式子表示下一个字符和当前字符是连着的（即按yizhong顺序），第六个式子表示可以搜到 ‘g’（因为本题递归是逐层返回1的）
		book[x][y] = 1;         //标记该点为1
		return 1;
	}
	return 0;               //前面没有返回1，说明没有搜到最后的‘g’，这里则返回0

}


int main(){
	int i, j, k;                 
	nextalp['y'] = 'i';  nextalp['i'] = 'z';  nextalp['z'] = 'h';   //一妙：nextalp数组以字符为下标，表示这个下标字符的下一个字符（将yizhong串起来）
	nextalp['h'] = 'o';  nextalp['o'] = 'n';  nextalp['n'] = 'g';
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%s", a[i]);

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (a[i][j] == 'y')             
				for (k = 0; k < 8; k++)           //二妙：分别八个方向搜索
					dfs(i, j, a[i][j], k);

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			if (book[i][j])              //如果标记为1就输出它本身
				printf("%c", a[i][j]);
			else                     //否则输出 ‘*’
				printf("*"); 
		printf("\n");               //每行输出后换行
	}

	return 0;
}