只拿80,用的普通循环做的,找不到那个细节的错误求大佬指正
查看原帖
只拿80,用的普通循环做的,找不到那个细节的错误求大佬指正
468594
XuHongXiang楼主2021/8/6 14:13

过不去那个AC的n是100,但是我一直没找到错误所在

//单词方阵问题,此题不用dfs来写,因为一旦找对方向直接沿着哪个方向遍历下去,根本不用回溯所以不用dfs
#include<iomanip>
#include<iostream>
#include<string>
using namespace std;
//定义两个数组,一个来存储单词方阵,一个来标记访问的点
char picture[110][110];
bool vis[110][110];
//n维方阵
int n;
//定义一个二维数组来分别搜索八个方向,这里重点类比搜索四个方向用了一维数组,搜索八个方向用一个二维数组
int dir[8][2] = { {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1} ,{-1,-1}, {-1,0}, {-1,1} };
//定义一个字符数组来存储所找对象
string goal = "yizhong";
void dfs(int x,int y)
{
	int k;//用k来找方向
	int i;//作为循环控制变量
	int dx, dy;
	for (k = 0; k < 8; k++)
	{
		dx = x + dir[k][0];
		dy = y + dir[k][1];
	/*	if (!((dx>=1) && (dx<=n) && (dy>=1) && (dy<=n)))
		{
			break;
		}*/
		if (picture[dx][dy] == 'i')
		{
			for (i = 2; i <= 6; i++)
			{
				dx = dx + dir[k][0];
				dy = dy + dir[k][1];
			/*	if (dx > n||dy > n||dx <= 0 || dy <= 0)
				{
					break;
				}*/
				if (picture[dx][dy] != goal[i])
				{
					break;
				}
			}
			if (i == 7)  //如果往那个方向走一直成立则说明确实相等,然后再标记刚才的那几个数组
			{
				vis[x][y] = 1;
				for (int j =1; j <= 6; j++)
				{
					x = x + dir[k][0];
					y = y + dir[k][1];
					vis[x][y] = 1;
				}
				return;
			}
		}
	}
}
int main()
{
	cin >> n;
	//用一个二重循环来读取单词方阵
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> picture[i][j];
		}
	}
	//以下正式开始搜索,先来个二重循环遍历图中的每个点
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (picture[i][j] == 'y')
			{
				dfs(i, j);
			}
		}
	}
	//最后记得循环输出最后的结果
	//cout << endl;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (vis[i][j])
			{
				cout << picture[i][j];
			}
			else
			{
				cout << '*';
			}
		}
		cout << endl;
	}
	//system("pause");
}

2021/8/6 14:13
加载中...