P1101 单词方阵

大致题意:

• 找出沿同一方向连续摆放的yizhong字符串，其它字符变为*。

基本思路:

• 一顿深搜操作猛如虎，一交OJ上面AC出。
• 我还真有文采啊啧啧啧。
• 好了不废话了，说出我的思路！
• 如果在字符矩阵中发现了y这个字符，然后找找周围有没有i字符，如果找到了，有戏！dfs！。
• dfs中，继续搜索yizhong，若搜索完毕，则把每个字符所在的位置标记。

Code:

//又是远古时期的码风...见谅
#include <iostream>
#include <cstdio>
using namespace std;
char m[110][110];
bool m_[110][110];
char k[8]="yizhong";
int n;
int x[7],y[7];
int dx[8]={0,0,-1,1,-1,-1,1,1};
int dy[8]={-1,1,0,0,-1,1,-1,1};
void dfs(int idx,int idy,int cnt,int f){
    if(cnt==7){//找完了
        for(int i=0;i<7;++i){//标记
            m_[x[i]][y[i]]=true;
        }
    }else{
        if(cnt==6||m[idx+dx[f]][idy+dy[f]]==k[cnt+1]&&idx+dx[f]<n&&idx+dx[f]>=0&&idy+dy[f]<n&&idy+dy[f]>=0){//如果下一个目标可行
            x[cnt]=idx;
            y[cnt]=idy;//记录
            dfs(idx+dx[f],idy+dy[f],cnt+1,f);//继续搜索
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>m[i][j];
        }
    }//输入
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(m[i][j]==‘y‘){//如果看到了‘y‘
                for(int p=0;p<8;++p){//康康有没有‘i‘
                    if(m[i+dx[p]][j+dy[p]]==‘i‘){//有，有戏！
                        dfs(i,j,0,p);//搜索，p是方向
                    }
                }
            }
        }
    }
    for(int i=0;i<n;++i){//最后输出
        for(int j=0;j<n;++j){
            if(m_[i][j]==true){
                cout<<m[i][j];
            }else{
                cout<<‘*‘;
            }
        }
        cout<<endl;
    }
    return 0;
}

P1101 单词方阵

原文：https://www.cnblogs.com/FUXyao/p/12885569.html