字符迷陣是一種經(jīng)典的智力游戲。玩家需要在給定的矩形的字符迷陣中尋找特定的單詞。 在這題的規(guī)則中，單詞是如下規(guī)定的： 1. 在字符迷陣中選取一個字符作為單詞的開頭； 2. 選取右方、下方、或右下45度方向作為單詞的延伸方向； 3. 以開頭的字符，以選定的延伸方向，把連續(xù)得到的若干字符拼接在一起，則稱為一個單詞。 以圖1為例，如果要在其中尋找單詞"WORD"，則綠色框所標(biāo)示的都是合法的方案，而紅色框所標(biāo)示的都是不合法的方案。 現(xiàn)在的問題是，給出一個字符迷陣，及一個要尋找的單詞，問能在字符迷陣中找到多少個該單詞的合法方案。注意合法方案是可以重疊的，如圖1所示的字符迷陣，其中單詞"WORD"的合法方案有4種。輸入描述: 輸入的第一行為一個正整數(shù)T，表示測試數(shù)據(jù)組數(shù)。 接下來有T組數(shù)據(jù)。每組數(shù)據(jù)的第一行包括兩個整數(shù)m和n，表示字符迷陣的行數(shù)和列數(shù)。接下來有m行，每一行為一個長度為n的字符串，按順序表示每一行之中的字符。再接下來還有一行包括一個字符串，表示要尋找的單詞。 數(shù)據(jù)范圍： 對于所有數(shù)據(jù)，都滿足1<=T<=9，且輸入的所有位于字符迷陣和單詞中的字符都為大寫字母。要尋找的單詞最短為2個字符，最長為9個字符。字符迷陣和行列數(shù)，最小為1，最多為99。 對于其中50%的數(shù)據(jù)文件，字符迷陣的行列數(shù)更限制為最多為20。輸出描述: 對于每一組數(shù)據(jù)，輸出一行，包含一個整數(shù)，為在給定的字符迷陣中找到給定的單詞的合法方案數(shù)。輸入例子1: 3 10 10 AAAAAADROW WORDBBBBBB OCCCWCCCCC RFFFFOFFFF DHHHHHRHHH ZWZVVVVDID ZOZVXXDKIR ZRZVXRXKIO ZDZVOXXKIW ZZZWXXXKIK WORD 3 3 AAA AAA AAA AA 5 8 WORDSWOR ORDSWORD RDSWORDS DSWORDSW SWORDSWO SWORD輸出例子1: 4 16 5

代碼：

#include<bits/stdc++.h> #include<vector>using namespace std; char a[100][100]; int main(){int _;cin>>_;while(_--){int m,n;string t;cin>>m>>n;cin.ignore();string pp;int count = 0;for(int i = 0;i<m;i++){getline(cin,pp);for(int j = 0;j < n;j++){a[i][j] = pp[j];}}/* for(int i = 0;i<m;i++){for(int j = 0;j < n;j++){cout<<a[i][j]<<" ";}cout<<endl;}*/getline(cin,t);int size = t.length();// cout<<"size:"<<size<<endl;for(int i = 0;i<m;i++){for(int j = 0;j < n-size+1;j++){bool flag = true;for(int h=j,k = 0;k<size;k++,h++){if(a[i][h] != t[k]){flag = false;break;}}if(flag)count++;}}// cout<<count<<endl;for(int i = 0;i<m-size+1;i++){// bool flag = true;for(int j = 0;j < n;j++){bool flag = true;for(int h=i,k = 0;k<size;k++,h++){if(a[h][j] != t[k]){flag = false;break;}}if(flag)count++;}}// cout<<count<<endl;for(int i = 0;i<m-size+1;i++){for(int j = 0;j < n-size+1;j++){bool flag = true;for(int h=i,u=j,k = 0;k<size;k++,h++,u++){if(a[h][u] != t[k]){flag = false;break;}}if(flag)count++;}}cout<<count<<endl;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lyf-sunicey/p/9392878.html

總結(jié)

以上是生活随笔為你收集整理的[编程题] 字符迷阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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