2020-09-21 单词方阵

https://www.luogu.com.cn/problem/P1101

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

//template<typename DataType>
//DataType qmi(DataType m, int k)
//{
//    DataType res = 1, t = m;
//    while (k)
//    {
//        if (k&1) res = res * t;
//        t = t * t;
//        k >>= 1;
//    }
//    return res;
//}


int qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

#define fi(a,b) for(int i = a; i < b; i++)
#define fie(a,b) for(int i = a; i <= b; i++)
#define fj(a,b) for(int j = a; j >= b; j--)


char map[10000][10000];
//bit数组表示的是行；
int total = 0;//总数:记录解的总数
int n,m;//输入的数，即N*N的格子，全局变量，搜索中要用
int found = 0;
int cnt = 0;

string key = "yizhong";


void out(){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j< m ; j++) {
            cout<<map[i][j];
        }
        cout<<endl;
    }
    cout<<endl;
}
//搜索与回溯主体
int dfs(int x,int y,int k,int type){
    
    if (map[x][y] == key[k]) {//找到了
        map[x][y] = '0'+k;//表示已经用过了
        bool isFound = false;//没有任何一个是匹配的
        found = 0;
        if(y - 1 >= 0 && (type == 1 || type == 0))
            if((found = dfs(x,y - 1,k+1 ,1)) == 0){//左
                
            }
        
        if(!isFound)
            isFound = found;
        //out();
        
        if(y + 1 < m && (type == 2 || type == 0))
            if((found = dfs(x,y + 1,k+1,2))==0){//右
                found = 0;//表示一个
            }
        
        //out();
        if(!isFound)
            isFound = found;
        
        if(x - 1 >= 0 && (type == 3 || type == 0))
            if((found = dfs(x - 1,y,k+1,3))==0){
                
            }
        
        //out();
        if(!isFound)
        isFound = found;
        
        if(x + 1 < n && (type == 4 || type == 0))
            if((found = dfs(x + 1,y,k+1,4)) == 0){
                
                
            }
        
        //out();
        if(!isFound)
        isFound = found;
        
        
        if(y - 1 >= 0 && x - 1 >= 0 && (type == 5 || type == 0))
            if((found = dfs(x - 1,y - 1,k+1,5))==0){
                
               
            }
        
        //out();
        if(!isFound)
        isFound = found;
        
        if(y - 1 >= 0 && x + 1 < n && (type == 6 || type == 0))
            if((found = dfs(x + 1,y - 1,k+1,6)) == 0){
                
                
            }
        
        //out();
        if(!isFound)
        isFound = found;
        
        if(y + 1 < m && x + 1 < n && (type == 7 || type == 0))
            if((found = dfs(x + 1,y + 1,k+1,7)) == 0){
               
                
            }
        
        //out();
        if(!isFound)
            isFound = found;
        
        if(y + 1 < m && x - 1 >= 0 && (type == 8 || type == 0))
            if((found = dfs(x - 1,y + 1,k+1,8)) ==0){
                
                
            }
        
        if (!isFound && k!=6) {
            map[x][y] = key[k];//没找到后续的
            return 0;
        }
        
        return 1;//查找成功的
    } else {
        return 0;//查找失败的
    }
}

int main()
{
    n = read();
    m = n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j< m ; j++) {
            cin>>map[i][j];
        }
    }
    
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j< m ; j++) {
            dfs(i,j,0,0);//深度优先搜索
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j< m ; j++) {
            switch (map[i][j]) {
                case '0':
                    map[i][j] = 'y';
                    break;
                 case '1':
                    map[i][j] = 'i';
                    break;
                case '2':
                    map[i][j] = 'z';
                    break;
                case '3':
                    map[i][j] = 'h';
                    break;
                case '4':
                    map[i][j] = 'o';
                    break;
                case '5':
                    map[i][j] = 'n';
                    break;
                case '6':
                    map[i][j] = 'g';
                    break;
                default:
                    map[i][j] = '*';
                    break;
            }
            cout<<map[i][j];
        }
        cout<<endl;
    }
    
    return 0;
}
/*
7
gffffff
ndddddd
ogggggg
hgfeddd
zffssaa
iggdssa
yffddww
============
3
*/