洛谷 P1101 單詞方陣

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

?

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

?

輸入輸出格式

輸入格式：

第一行輸入一個數n。(7≤n≤100)。

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

輸出格式：

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

輸入輸出樣例

輸入樣例1：

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
輸出樣例：

*******
*******
*******
*******
*******
*******
*******
輸入樣例2：

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

輸出樣例：

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

?

提供兩種解法 一種是dfs 一種是暴力 要是只想把這個題ac掉的話直接往下看暴力法就好了 想練一練dfs的可以好好看看解法一

解法一（dfs）：

?

#include<bits/stdc++.h>using namespace std;char m[105][105],a[]="yizhong",ans[105][105];
int n,f[2][8]={1,1,1,0,0,-1,-1,-1,1,0,-1,1,-1,1,0,-1};void dfs(int x,int y,int k,int p)  //x y 為當前坐標 k代表朝哪個方向搜 p代表是這個方向上的第幾個字母
{int i;if(p==6) {for(i=p;i>=0;i--)ans[x-i*f[0][k]][y-i*f[1][k]]=a[6-i];    //我用ans數組保存要輸出的“地圖”，如果有符合的字符串就記錄到ans里return;}else if(m[x+f[0][k]][y+f[1][k]]==a[p+1])     dfs(x+f[0][k],y+f[1][k],k,p+1);          //沿著k方向搜 由于不會轉向別的方向 所以不需要vis數組判斷是否已經經過這個點 這是和其他的dfs區別最大的地方else return;    
}int main()
{int i,j,k;cin>>n;for(i=0;i<n;i++)cin>>m[i];for(i=0;i<n;i++)for(j=0;j<n;j++)ans[i][j]='*';     //對ans數組初始化 全部設為“*”for(i=0;i<n;i++)for(j=0;j<n;j++){if(m[i][j]=='y')for(k=0;k<8;k++){dfs(i,j,k,0);}}for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<ans[i][j];cout<<endl;}
}

?

解法二（暴力）：

#include<iostream>
#include<cstdio>
using namespace std;
string s[111],ans[111];
const int a[8]={0,-1,-1,-1,0,1,1,1},b[8]={1,1,0,-1,-1,-1,0,1};
int t1,t2,kk,k,i,j,n;
bool bb;
int main()
{cin>>n;for (i=1; i<=n; i++) cin>>s[i];for (i=1; i<=n; i++)for (j=1; j<=n; j++)ans[i]+='0';for (i=1; i<=n; i++)for (j=0; j<=n-1; j++)if (s[i][j]=='y') {for (k=0; k<=7; k++){t1=i;  t2=j;bb=1;for (kk=1; kk<=6; kk++){t1+=a[k]; t2+=b[k];if (t1<1||t1>n||t2<0||t2>n-1) bb=0;if (bb==0) break;if (kk==1&&s[t1][t2]!='i') bb=0;if (kk==2&&s[t1][t2]!='z') bb=0;if (kk==3&&s[t1][t2]!='h') bb=0;if (kk==4&&s[t1][t2]!='o') bb=0;if (kk==5&&s[t1][t2]!='n') bb=0;if (kk==6&&s[t1][t2]!='g') bb=0;} t1=i; t2=j;if (bb) for (kk=0; kk<=6; kk++) ans[t1][t2]=s[t1][t2],t1+=a[k],t2+=b[k];}}for (i=1; i<=n; i++)for (j=0; j<=n-1; j++)if (ans[i][j]=='0') ans[i][j]='*';for (i=1; i<=n; i++)cout<<ans[i]<<endl;return 0;
}

?

解法二是別人的題解 直接拿來用了 可以更優化一點的 不過沒必要了 都可以ac

?