題目描述

給一n \times nn×n的字母方陣，內(nèi)可能蘊含多個“yizhong”單詞。單詞在方陣中是沿著同一方向連續(xù)擺放的。擺放可沿著?88?個方向的任一方向，同一單詞擺放時不再改變方向，單詞與單詞之間可以交叉,因此有可能共用字母。輸出時，將不是單詞的字母用*代替，以突出顯示單詞。例如：

輸入：8 輸出：qyizhong *yizhonggydthkjy gy******nwidghji n*i*****orbzsfgz o**z****hhgrhwth h***h***zzzzzozo z****o**iwdfrgng i*****n*yyyygggg y******g

輸入輸出格式

輸入格式：

?

第一行輸入一個數(shù)nn。(7 \le n \le 1007≤n≤100)。

第二行開始輸入n \times nn×n的字母矩陣。

?

輸出格式：

?

突出顯示單詞的n \times nn×n矩陣。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制

7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa

輸出樣例#1：?復(fù)制

******* ******* ******* ******* ******* ******* *******

輸入樣例#2：?復(fù)制

8 qyizhong gydthkjy nwidghji orbzsfgz hhgrhwth zzzzzozo iwdfrgng yyyygggg

輸出樣例#2：?復(fù)制

*yizhong gy****** n*i***** o**z**** h***h*** z****o** i*****n* y******g

?

作者:?hzg0226

#include <iostream> #include <memory.h> using namespace std;const int maxn = 100+10; struct node {int x, y; }c[maxn];int n; char map[maxn][maxn], str[] = "yizhong"; int vis[maxn][maxn]; int dir[][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};void dfs(int x, int y, node c[], int k, int cur) {if(cur == 7){for(int i = 0; i < 7; i++){vis[c[i].x][c[i].y] = 1; //把路徑進行標(biāo)記}}else{int dx = x + dir[k][0];int dy = y + dir[k][1];if(cur == 6 || map[dx][dy] == str[cur+1]) //能夠匹配，就記錄下路徑{c[cur].x = x, c[cur].y = y;dfs(dx,dy,c,k,cur+1); //繼續(xù)遞歸}} }int main() {scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%s", &map[i]);}memset(vis,0,sizeof(vis));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(map[i][j] == 'y'){for(int k = 0; k < 8; k++){int x = i + dir[k][0];int y = j + dir[k][1];if(map[x][y] == 'i') //找到正確的方向，按著正確的那個方向進行遞歸！dfs(i,j,c,k,0);}}}}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(vis[i][j]) printf("%c", map[i][j]);else printf("*");}printf("\n");}return 0; }

這道題思來想去有思路，但是實現(xiàn)都很復(fù)雜。搜索一直是我的弱項，枯了。然后看了大牛的題解。

豁然開朗。

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的洛谷——P1101 单词方阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。