感觉思路没啥问题,只过了最后两个测试点,求大佬指点~
查看原帖
感觉思路没啥问题,只过了最后两个测试点,求大佬指点~
549907
Aheaddd楼主2022/8/28 22:57
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
int n;
char g[N][N];
bool st[N][N]; //标记每个点是否为单词中的字母
int dx[8] = {-1,-1,-1,0,1,1,1,0},dy[8] = {-1,0,1,1,1,0,-1,-1}; //八个方向的偏移量 
int directions[8] = {0,1,2,3,4,5,6,7}; //分别代表左上,上,右上,右,右下,下,左下,左八个方向 
char c[8] = "yizhong";

bool dfs(int x,int y,int u,int dire) //当前字母坐标为(x,y),合法字母u+1个,方向为dire 
{
	if(u == 7) //说明前面的字母都合法 
	{
		return true; //此句发生时,找到yizhong,从后往前return true,直到开头的y 
	}
	if(g[x][y] != c[u])//如果字母不合法
	{
		return false;
	}
	
	if(g[x][y] == c[u]) //如果当前字母合法,沿当前方向继续dfs 
	{
		int xx = x + dx[dire],yy = y + dy[dire];
		if(xx >= 0 && xx < n && yy >= 0 && yy < n)
		{
			if(dfs(xx,yy,u + 1,dire))
			{
				st[x][y] = true;
				return true;
			}
			else
				return false;
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			cin >> g[i][j]; //读入 
	
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			if(g[i][j] == 'y') //如果是y开头,则dfs八个方向
				for(int k = 0;k < 8;k++)
				{
					int x = i + dx[k],y = j + dy[k];
					if(x >= 0 && x < n && y >= 0 && y < n)
					{
						if(dfs(x,y,1,k))
							st[i][j] = true;						
					}
				}
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(st[i][j]) cout << g[i][j];
			else cout << '*' ;
		}
		cout << endl;
	}
	return 0;
}
2022/8/28 22:57
加载中...