洛谷P1101单词方阵（正向图的遍历搜索递归）

题目链接：https://www.luogu.org/problemnew/show/P1101

题目比较简单，就是用来练搜索dfs的。

没有什么难点，要说的话，就是把多条繁琐的if换成for循环形式。

循环形式

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <iomanip>
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <cmath>
  8 using namespace std;
  9 typedef long long ll;
 10 typedef unsigned long long ull;
 11 const int maxn=105;
 12 const int maxm=105;
 13 const int inf=1e9;
 14 char a[maxn][maxn],c[maxn][maxn];
 15 char b[7]={'y','i','z','h','o','n','g'};
 16 int n;
 17 
 18 void Init()
 19 {
 20     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]='*';
 21 }
 22 
 23 void so1(int x,int y)
 24 {
 25     int j=0,p=1;
 26     for(j=y+1;j<=y+6;j++)
 27     {
 28         if(a[x][j]!=b[p]) return;
 29         else p++;
 30     }
 31 
 32     c[x][y]='y'; p=1;
 33     for(int j=y+1;j<=y+6;j++) c[x][j]=b[p++];
 34 }
 35 void so2(int x,int y)
 36 {
 37     int i=0,p=1;
 38     for(i=x+1;i<=x+6;i++)
 39     {
 40         if(a[i][y]!=b[p]) return;
 41         else p++;
 42     }
 43 
 44     c[x][y]='y'; p=1;
 45     for(int i=x+1;i<=x+6;i++) c[i][y]=b[p++];
 46 }
 47 void so3(int x,int y)
 48 {
 49     int i=0,p=1;
 50     for(i=x-1;i>=x-6;i--)
 51     {
 52         if(a[i][y]!=b[p]) return;
 53         else p++;
 54     }
 55 
 56     c[x][y]='y'; p=1;
 57     for(int i=x-1;i>=x-6;i--) c[i][y]=b[p++];
 58 }
 59 void so4(int x,int y)
 60 {
 61     int j=0,p=1;
 62     for(j=y-1;j>=y-6;j--)
 63     {
 64         if(a[x][j]!=b[p]) return;
 65         else p++;
 66     }
 67 
 68     c[x][y]='y'; p=1;
 69     for(int j=y-1;j>=y-6;j--) c[x][j]=b[p++];
 70 }
 71 void so5(int x,int y)
 72 {
 73     int i=0,j=0,p=1;
 74     for(i=x-1,j=y+1;j<=y+6;j++,i--)
 75     {
 76         if(a[i][j]!=b[p]) return;
 77         else p++;
 78     }
 79 
 80     c[x][y]='y'; p=1;
 81     for(i=x-1,j=y+1;j<=y+6;j++,i--) c[i][j]=b[p++];
 82 }
 83 void so6(int x,int y)
 84 {
 85     int i=0,j=0,p=1;
 86     for(i=x+1,j=y+1;j<=y+6;j++,i++)
 87     {
 88         if(a[i][j]!=b[p]) return;
 89         else p++;
 90     }
 91 
 92     c[x][y]='y'; p=1;
 93     for(i=x+1,j=y+1;j<=y+6;j++,i++) c[i][j]=b[p++];
 94 }
 95 void so7(int x,int y)
 96 {
 97     int i=0,j=0,p=1;
 98     for(i=x-1,j=y-1;j<=y+6;j--,i--)
 99     {
100         if(a[i][j]!=b[p]) return;
101         else p++;
102     }
103 
104     c[x][y]='y'; p=1;
105     for(i=x-1,j=y-1;j<=y+6;j--,i--) c[i][j]=b[p++];
106 }
107 void so8(int x,int y)
108 {
109     int i=0,j=0,p=1;
110     for(i=x+1,j=y-1;j<=y+6;j--,i++)
111     {
112         if(a[i][j]!=b[p]) return;
113         else p++;
114     }
115 
116     c[x][y]='y'; p=1;
117     for(i=x+1,j=y-1;j<=y+6;j--,i++) c[i][j]=b[p++];
118 }
119 
120 int main()
121 {
122     ios::sync_with_stdio(false); cin.tie(0);
123 
124     cin>>n;
125     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
126 
127     Init();
128     for(int i=1;i<=n;i++)
129     {
130         for(int j=1;j<=n;j++)
131         {
132             if(a[i][j]=='y')
133             {
134                 if(j+6<=n) so1(i,j);//右
135                 if(i+6<=n) so2(i,j);//下
136                 if(i-6>=1) so3(i,j);//上
137                 if(j-6>=1) so4(i,j);//左
138                 if(i-6>=1 && j+6<=n) so5(i,j);//右上
139                 if(i+6<=n && j+6<=n) so6(i,j);//右下
140                 if(i-6>=1 && j-6>=1) so7(i,j);//左上
141                 if(i+6<=n && j-6>=1) so8(i,j);//左下
142             }
143         }
144     }
145 
146     for(int i=1;i<=n;i++)
147     {
148         for(int j=1;j<=n;j++)
149         {
150             cout<<c[i][j];
151         }
152         cout<<endl;
153     }
154 
155     return 0;
156 }

递归dfs形式（多条if代表多个方向）

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <iomanip>
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <cmath>
  8 using namespace std;
  9 typedef long long ll;
 10 typedef unsigned long long ull;
 11 const int maxn=105;
 12 const int maxm=105;
 13 const int inf=1e9;
 14 char a[maxn][maxn],c[maxn][maxn];
 15 char b[7]={'y','i','z','h','o','n','g'};
 16 int n;
 17 
 18 void Init()
 19 {
 20     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]='*';
 21 }
 22 
 23 
 24 void so1(int x,int y,int p)
 25 {
 26     if(p>6)
 27     {
 28         int pp=0;
 29         for(int j=y-6-1;j<=y-1;j++) c[x][j]=b[pp++];
 30 
 31         return;
 32     }
 33 
 34     if(a[x][y]==b[p] && y+1<=n+1) so1(x,y+1,p+1);
 35 }
 36 void so2(int x,int y,int p)
 37 {
 38     if(p>6)
 39     {
 40         int pp=0;
 41         for(int i=x-6-1;i<=x-1;i++) c[i][y]=b[pp++];
 42 
 43         return;
 44     }
 45 
 46     if(a[x][y]==b[p] && x+1<=n+1) so2(x+1,y,p+1);
 47 }
 48 void so3(int x,int y,int p)
 49 {
 50     if(p>6)
 51     {
 52         int pp=0;
 53         for(int i=x+6+1;i>=x+1;i--) c[i][y]=b[pp++];
 54 
 55         return;
 56     }
 57 
 58     if(a[x][y]==b[p] && x-1>=0) so3(x-1,y,p+1);
 59 }
 60 void so4(int x,int y,int p)
 61 {
 62     if(p>6)
 63     {
 64         int pp=0;
 65         for(int j=y+6+1;j>=y+1;j--) c[x][j]=b[pp++];
 66 
 67         return;
 68     }
 69 
 70     if(a[x][y]==b[p] && y-1>=0) so4(x,y-1,p+1);
 71 }
 72 
 73 void so5(int x,int y,int p)
 74 {
 75     if(p>6)
 76     {
 77         int pp=0;
 78         for(int i=x+6+1,j=y-6-1;j<=y-1;i--,j++) c[i][j]=b[pp++];
 79 
 80         return;
 81     }
 82 
 83     if(a[x][y]==b[p] && x-1>=0 && y+1<=n+1) so5(x-1,y+1,p+1);
 84 }
 85 void so6(int x,int y,int p)
 86 {
 87     if(p>6)
 88     {
 89         int pp=0;
 90         for(int i=x-6-1,j=y-6-1;j<=y-1;i++,j++) c[i][j]=b[pp++];
 91 
 92         return;
 93     }
 94 
 95     if(a[x][y]==b[p] && x+1<=n+1 && y+1<=n+1) so6(x+1,y+1,p+1);
 96 }
 97 void so7(int x,int y,int p)
 98 {
 99     if(p>6)
100     {
101         int pp=0;
102         for(int i=x+6+1,j=y+6+1;j>=y+1;i--,j--) c[i][j]=b[pp++];
103 
104         return;
105     }
106 
107     if(a[x][y]==b[p] && x-1>=0 && y-1>=0) so7(x-1,y-1,p+1);
108 }
109 void so8(int x,int y,int p)
110 {
111     if(p>6)
112     {
113         int pp=0;
114         for(int i=x-6-1,j=y+6+1;j>=y+1;i++,j--) c[i][j]=b[pp++];
115 
116         return;
117     }
118 
119     if(a[x][y]==b[p] && x+1<=n+1 && y-1>=0) so8(x+1,y-1,p+1);
120 }
121 
122 int main()
123 {
124     ios::sync_with_stdio(false); cin.tie(0);
125 
126     cin>>n;
127     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
128 
129     Init();
130     for(int i=1;i<=n;i++)
131     {
132         for(int j=1;j<=n;j++)
133         {
134             if(a[i][j]=='y')
135             {
136                 if(j+6<=n) so1(i,j+1,1);//右
137                 if(i+6<=n) so2(i+1,j,1);//下
138                 if(i-6>=1) so3(i-1,j,1);//上
139                 if(j-6>=1) so4(i,j-1,1);//左
140                 if(i-6>=1 && j+6<=n) so5(i-1,j+1,1);//右上
141                 if(i+6<=n && j+6<=n) so6(i+1,j+1,1);//右下
142                 if(i-6>=1 && j-6>=1) so7(i-1,j-1,1);//左上
143                 if(i+6<=n && j-6>=1) so8(i+1,j-1,1);//左下
144             }
145         }
146     }
147 
148     for(int i=1;i<=n;i++)
149     {
150         for(int j=1;j<=n;j++)
151         {
152             cout<<c[i][j];
153         }
154         cout<<endl;
155     }
156 
157     return 0;
158 }

精简化递归dfs形式（把方向存在数组里代替多条if）

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int maxn=105;
12 const int maxm=105;
13 const int inf=1e9;
14 char a[maxn][maxn],c[maxn][maxn];//输入数组,保存答案数组
15 char b[7]={'y','i','z','h','o','n','g'};//需要判断的字符串
16 int X[8]={0,1,-1,0,-1,1,-1,1};//8个方向
17 int Y[8]={1,0,0,-1,1,1,-1,-1};
18 int n;//大小
19 int f;//标记回溯改变答案
20 
21 void Init()
22 {
23     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]='*';
24 }
25 
26 void so(int x,int y,int p,int kk)
27 {
28     if(p>6)
29     {
30         f=1;//成功,有这个单词
31         return;
32     }
33 
34     int nx=x+X[kk],ny=y+Y[kk];
35     if(a[nx][ny]==b[p] && nx>=0&&nx<=n+1 && ny>=0&&ny<=n+1) so(nx,ny,p+1,kk);//下一个方向
36     if(f) c[nx][ny]=b[p];//回溯,改变路径得到正确答案
37 }
38 
39 
40 int main()
41 {
42     ios::sync_with_stdio(false); cin.tie(0);
43 
44     cin>>n;
45     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
46 
47     Init();
48     for(int i=1;i<=n;i++)
49     {
50         for(int j=1;j<=n;j++)
51         {
52             if(a[i][j]=='y')
53             {
54                 for(int k=0;k<=7;k++)
55                 {
56                     f=0;
57                     so(i,j,1,k);
58                     if(f) c[i][j]='y';
59                 }
60             }
61         }
62     }
63 
64     for(int i=1;i<=n;i++)
65     {
66         for(int j=1;j<=n;j++)
67         {
68             cout<<c[i][j];
69         }
70         cout<<endl;
71     }
72 
73     return 0;
74 }

完。