洛谷 P1101 单词方阵

## 本萌新又来发布题解了

## 这一题，我们用搜索染色

## 在此提供一简易代码：

预处理：

int c[10000][2],d=0;//c[10000][2]用来存 “y”出现的地址 
int x[9]={0,1,0,1,-1,0,-1,1,-1};//八个方位 
int y[9]={0,0,1,1,0,-1,-1,-1,1};//方便比对 
char a[103][103],b,k[9]=" yizhong";
bool s[102][102];//定义染色体，“0”输出“*” ，“1”正常输出 

搜索函数：

bool f(int i,int j,int m,int n,int next){//i,j为数组位置，m,n是方位 
	if(next>=8){//next是“yizhong”的第几个字符 
		s[i][j]=1;//比对完毕，进行染色； 
		return 1;//返回 
	}
	if(a[i+m][j+n]==k[next])//如果该位置上的字符与对应字符一致，则继续 
	    if(f(i+m,j+n,m,n,next+1)){
	    	s[i][j]=1;//染色 
	    	return 1;//返回上一层
		}
	return 0;//不一致，则结束 

输入：

int n,i,j,o;
	cin>>n;
	for(i=1;i<=n;i++){
	    for(j=1;j<=n;j++){
			cin>>b;
			a[i][j]=b;//输入字符 
			if(b=='y'){
				c[++d][0]=i;//记录“y”的位置 
				c[d][1]=j;//d为“y”的个数 
			}
		}
	}

全方位搜索：

while(d){
		i=c[d][0];
		j=c[d][1];
		for(o=1;o<=8;o++){//全方位递归搜索 
		   if(a[i+x[o]][j+y[o]]=='i')
		     if(f(i+x[o],j+y[o],x[o],y[o],3))
		         s[i][j]=1;
		}
		d--;

输出：

for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(s[i][j])//染了色，便正常输出 
			cout<<a[i][j];
			else cout<<"*";//否则输出“*” 
		}
		cout<<endl;
	}

你们最爱的完整代码：

#include<iostream>
using namespace std;
int c[10000][2],d=0,x[9]={0,1,0,1,-1,0,-1,1,-1};
int                 y[9]={0,0,1,1,0,-1,-1,-1,1};
char a[103][103],b,k[9]=" yizhong";
bool s[102][102];
bool f(int i,int j,int m,int n,int next){
    if(next>=8){
        s[i][j]=1;
        return 1;
    }
    if(a[i+m][j+n]==k[next])
        if(f(i+m,j+n,m,n,next+1)){
        	s[i][j]=1;
        	return 1;
        }
    return 0;
}
int main(){
    int n,i,j,o;
    cin>>n;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            cin>>b;
            if(b=='y'){
                c[++d][0]=i;
                c[d][1]=j;
            }
            a[i][j]=b;
        }
    }
    while(d){
        i=c[d][0];
        j=c[d][1];
        for(o=1;o<=8;o++){
           if(a[i+x[o]][j+y[o]]=='i')
              if(f(i+x[o],j+y[o],x[o],y[o],3))
                 s[i][j]=1;
        }
        d--;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(s[i][j])cout<<a[i][j];
            else cout<<"*";
        }
        cout<<endl;
    }
    return 0;
}

码字挺不容易，大家点个赞再走吧^◇0/。