洛谷P1101 單詞方陣 （DFS）

題目位址

https://www.luogu.com.cn/problem/P1101

思路

dfs即可，這個資料量暴力遞推也行

AC代碼

#include <iostream>
using namespace std;
int n;
char mark[] = "yizhong";//驗證字元串
string a[105];
int visited[105][105];
int dx[] = { 0,0,1,0,-1,1,1,-1,-1 };//八個方向
int dy[] = { 0,-1,0,1,0,1,-1,-1,1 };
pair <int, int>road[105];
void dfs(int x, int y,int step,int dirction)//step記錄步數，dirction記錄要往哪裡走
{
	if(a[x][y]=='g'&&step==6)//走到頂了
	{
		for(int i=0;i<7;i++)
		{
			visited[road[i].first][road[i].second] = 1;//标記！
		}
		return;
	}
	
	if(dirction==0)//如果是dfs的開端
	{
		road[step] = { x,y };
		for(int i=1;i<=8;i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<n&&a[nx][ny]==mark[step+1])
			{//往八個點找一個合法的進去遞歸
				road[step+1] = { nx,ny };
				dfs(nx, ny, step + 1, i);//i即下次遞歸的方向
			}
		}
	}
	else
	{
		int nx = x + dx[dirction];
		int ny = y + dy[dirction];
		if (nx >= 0 && nx < n && ny >= 0 && ny < n && a[nx][ny] == mark[step + 1])
		{
			road[step + 1] = { nx,ny };
			dfs(nx, ny, step + 1, dirction);
		}
	}


}
int main(int argc, char* argv[])
{
	cin >> n;

	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		if (a[i] == "\n")
			cin >> a[i];
	}

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(a[i][j] == 'y')
			{
				dfs(i, j, 0, 0);//找一個y開始dfs
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (visited[i][j]==1)
			{
				cout << a[i][j];//被标記的原樣輸出
			}
			else
			{
				cout << '*';
			}
		}
		cout << endl;
	}
	return 0;
}

           

心得：水題，簡單考驗了dfs的設計，but運勢寄了