客户问 你们网站怎么做的,云南建设银行官方网站,网站建设开发,网站开发团队排行榜给一nn的字母方阵#xff0c;内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8个方向的任一方向#xff0c;同一单词摆放时不再改变方向#xff0c;单词与单词之间可以交叉,因此有可能共用字母。输出时#xff0c;将不是单词的字母用*代… 给一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 7aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa输出样例 *************************************************输入样例2 8qyizhonggydthkjynwidghjiorbzsfgzhhgrhwthzzzzzozoiwdfrgngyyyygggg 输出样例 *yizhonggy******n*i*****o**z****h***h***z****o**i*****n*y******g 提供两种解法 一种是dfs 一种是暴力 要是只想把这个题ac掉的话直接往下看暴力法就好了 想练一练dfs的可以好好看看解法一 解法一dfs #includebits/stdc.husing 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(p6) {for(ip;i0;i--)ans[x-i*f[0][k]][y-i*f[1][k]]a[6-i]; //我用ans数组保存要输出的“地图”如果有符合的字符串就记录到ans里return;}else if(m[xf[0][k]][yf[1][k]]a[p1]) dfs(xf[0][k],yf[1][k],k,p1); //沿着k方向搜 由于不会转向别的方向 所以不需要vis数组判断是否已经经过这个点 这是和其他的dfs区别最大的地方else return;
}int main()
{int i,j,k;cinn;for(i0;in;i)cinm[i];for(i0;in;i)for(j0;jn;j)ans[i][j]*; //对ans数组初始化 全部设为“*”for(i0;in;i)for(j0;jn;j){if(m[i][j]y)for(k0;k8;k){dfs(i,j,k,0);}}for(i0;in;i){for(j0;jn;j)coutans[i][j];coutendl;}
} 解法二暴力 #includeiostream
#includecstdio
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()
{cinn;for (i1; in; i) cins[i];for (i1; in; i)for (j1; jn; j)ans[i]0;for (i1; in; i)for (j0; jn-1; j)if (s[i][j]y) {for (k0; k7; k){t1i; t2j;bb1;for (kk1; kk6; kk){t1a[k]; t2b[k];if (t11||t1n||t20||t2n-1) bb0;if (bb0) break;if (kk1s[t1][t2]!i) bb0;if (kk2s[t1][t2]!z) bb0;if (kk3s[t1][t2]!h) bb0;if (kk4s[t1][t2]!o) bb0;if (kk5s[t1][t2]!n) bb0;if (kk6s[t1][t2]!g) bb0;} t1i; t2j;if (bb) for (kk0; kk6; kk) ans[t1][t2]s[t1][t2],t1a[k],t2b[k];}}for (i1; in; i)for (j0; jn-1; j)if (ans[i][j]0) ans[i][j]*;for (i1; in; i)coutans[i]endl;return 0;
} 解法二是别人的题解 直接拿来用了 可以更优化一点的 不过没必要了 都可以ac 转载于:https://www.cnblogs.com/dyhaohaoxuexi/p/10617250.html
