（洛谷）第一个题组题解

本文主要是介绍（洛谷）第一个题组题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

八皇后问题

迷宫问题

自然数的拆分问题

填涂颜色

考前临时抱佛脚

PERKET

莱克计数

单词方阵

马的遍历

陨石雨

奇怪的电梯

玉米迷宫

单词接龙

八皇后问题

题目描述

一个如下的 6 \times 66×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5 来描述，第 ii 个数字表示在第 ii 行的相应位置有一个棋子，如下：

行号 1\ 2\ 3\ 4\ 5\ 61 2 3 4 5 6

列号 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式

一行一个正整数 n，表示棋盘是 n x n大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例

输入

输出

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

思路分析：

这道题目主要考查的是搜索和回溯。就是先找到所有符合条件的情况，然后把前三种情况输出来即可。

这道题需要定义四个数组，第一个数组为dir[],这个数组的作用是记录在行中，每个皇后的位置，数组中每一位上的数字代表的就是第几个皇后在当前行的位置。第二个数组是line[],这个数组用来记录当前列中有没有放置皇后。第三个数组是dui1[]，这个数组的作用就是记录左下到右上对角线中有没有放置皇后。第四个数组是dui2[]，这个数组的作用是记录右下到左上对角线中有没有放置皇后。

还需要定义两个函数，一个是搜索函数queen，这个函数中的第一个参数指的是当前行，所以应该从1开始，第二个参数指的是整个皇后地图是几行几列，因此不需要改变。还有一个函数是输出函数print，这个函数是用来当当前情况符合条件的时候，就调用该函数用来输出。由于题目要求只有输出前三个，因此只有小于等于3的时候才需要输出。

需要注意的部分就是回溯，每搜索完一次情况之后，要把各个数组中的元素清零，才能进入下一次的搜素。

代码实现：

#include<stdio.h>
#include<math.h>
int sum=0;//存储有多少中合法的放置方法
int dir[100];//记录每个皇后的位置
int line[100];//记录列上的位置
int dui1[100];//记录左下到右上的对角线
int dui2[100];//记录右下到左上的对角线
int n;//几行几列
void print(int n)
{     sum++;if(sum<=3)  //只要输出前三种情况{for(int i=1;i<=n;i++)printf("%d ",dir[i]);printf("\n"); } 
}
int  queen(int num,int n)
{for(int i=1;i<=n;i++)if(line[i]==0&&dui1[i+num]==0&&dui2[num-i]==0)//判断当前列有没有皇后，判断左下到右上对角线上有无皇后，因为该对角线中的行和列加起来相等。{                                          //判断右下到左上对角线上有无皇后，因为该对角线中的行列之差相等dir[num]=i;line[i]=1;    //由于在该位置上放置了皇后，因此就需要标记dui1[i+num]=1;dui2[num-i]=1;if(num==n)print(n);else queen(num+1,n);line[i]=0;     //回溯部分，当前情况结束，将位置清零dui1[i+num]=0;dui2[num-i]=0;}return 0;
}
int main()
{    int i;do{scanf("%d",&n);}while(n<6||n>13);//控制n的范围queen(1,n);printf("%d\n",sum);return 0;
}

迷宫问题

题目背景

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

题目描述

无

输入格式

第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式

给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

输入输出样例

输入

2 2 1
1 1 2 2
1 2

输出

思路分析：

这道题的主要思路就是定义两个数组，一个代表整个迷宫地图，1就是障碍物的位置，0代表可以走的位置。还有一个数组是用来标记走过的位置。

定义一个搜索函数，函数的两个参数代表的就是当前位置的横坐标和纵坐标，从起点坐标开始。判断：当前坐标是否等于终点坐标，如果到达的话，方案数就+1。没有到达的话，就定义一个循环，从上下左右四个方向判断，判断下一个位置是否有障碍或者是走过，判断下一个位置是否越界。如果以上两个条件都满足的话，就标记下一个位置为1，并且继续向下搜索。

再搜索完当前情况之后，需要回溯，就是要把走过的位置再重新清零，以便下一种方案的进行。

代码实现：

#include<stdio.h>
int map[100][100];//整个迷宫地图
int book[100][100];//用来标记是否走过
int sum;//记录方案数
int next[10][10]={{-1,0},{1,0},{0,-1},{0,1}};//用来存储上下左右四个方向
int fx,fy;//终点坐标
int n,m;//几行几列的迷宫
void dfs(int sx,int sy)
{if(sx==fx&&sy==fy)//如果当前坐标等于终点坐标，计数器就+1{sum++;}else{int tx,ty;//用来存储下一个要走的位置for(int i=0;i<4;i++){tx=sx+next[i][0];ty=sy+next[i][1];if(map[tx][ty]==1||book[tx][ty]==1)//判断下一个位置是否有障碍物或者已经被走过continue;if(tx<=0||tx>n||ty<=0||ty>m)//判断下一个位置是否越界continue;book[tx][ty]=1;//标记下一个位置为走过dfs(tx,ty);book[tx][ty]=0;//回溯：把走过的部分清零}}
}
int main()
{int t,sx,sy;scanf("%d %d %d",&n,&m,&t);//输入行数和列数以及障碍数scanf("%d %d %d %d",&sx,&sy,&fx,&fy);//输入起点坐标和终点坐标int zx,zy;//障碍点for(int i=0;i<t;i++){scanf("%d %d",&zx,&zy);map[zx][zy]=1;//将有障碍的地方标记为1，即不能走的位置}map[sx][sy]=1;//将起点坐标标记为走过dfs(sx,sy);printf("%d",sum);return 0;
}

自然数的拆分问题

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数n。

输出格式

输出：若干数的加法式子。

输入输出样例

输入

输出

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

思路分析

这道题考查的是回溯和递归搜索的运用。大致思路就是将能够组成n的数存入到数组中，当所有数的和等于n的时候就输出，并且要回溯到第一个数的情况。

定义一个函数，函数有三个参数分别为待拆分的自然数n、被拆分的数字序号（也就是存入数组的顺序，从0开始），以及数字加起来的和（从0开始）。然后循环从1到不大n的数，通过观察可以发现从第二个拆分的数字开始，每一位都大于等于前一位。因此这里需要判断，之前所有数的和加上当前数是否小于等于n、当前数是否大于前一位的数字。如果条件满足的话，就将当前数存入数组，并开始递归，第一个参数n不变，第二个参数要+1，因为数组当前位上已经存入数字，需要往后移，第三个参数需要加上当前数字。

递归判断条件是当前面所有数的和等于n的时候，就把数组中的数组按存入顺序输出即可。

代码实现：

#include<bits/stdc++.h>
int a[100];
void chai(int n,int count,int k)//n为待拆分的数，count为数组的序号，k为数字和
{    if(k==n)//如果数字和等于n{  for(int i=0;i<count;i++){if(i<count-1)printf("%d+",a[i]);else printf("%d",a[i]);}printf("\n");}else{for(int i=1;i<n;i++){if(i+k<=n&&count==0)//如果是第一个数并且数字和加上当前数小于等于n{   a[count]=i;//存入到数组中chai(n,count+1,k+i);//递归调用}else if(i+k<=n&&count>=0&&i>=a[count-1])//如果不是第一个数、数字和加上当前数小于等于n，并且当前数大于等于前一个数字{   a[count]=i;chai(n,count+1,k+i);}}}
}
int main()
{int n;scanf("%d",&n);chai(n,0,0);return 0;
}

填涂颜色

题目描述

由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)

接下来nn行，由00和11组成的n \times nn×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

输出格式

已经填好数字22的完整方阵。

输入输出样例

输入

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

思路分析：

题目要求把闭合圈中的0全部变成2，因此我们可以把闭合圈之外的0全部变成3，然后遍历地图，发现的0就全部都是闭合圈之内的0了，将其变成2即可，再将3变回为0。最后全部输出。

这里需要定义一个搜索函数，并且需要注意的是要在地图周围包一圈的0，然后从周围的任意位置开始搜索都可以，这样就可以避免四条边上有不是1，且那条边不是闭合圈的边。

在函数的一开始就判断当前位置是否为0，这里的作用是左上角为圈外0的情况，与后面的搜索没有关系。

在函数中向上下左右四个方向开始搜索，判断下一个位置如果是1，或者是3（已经被标记过的圈外0），就不递归。判断下一个位置如果越界，也不递归。如果上述两个条件都满足，就证明下一个位置为圈外0，因此将其赋为3，然后开始递归搜索。

代码实现：

#include<stdio.h>
int map[100][100];
int next[100][100]={{0,1},{0,-1},{1,0},{-1,0}};//四个搜索i方向
void dfs(int sx,int sy,int n)//函数三个参数分别代表当前位置的行、当前位置的列以及地图是几行几列的大小
{if(map[sx][sy]==0){ map[sx][sy]=3;}int tx,ty;for(int i=0;i<4;i++){  tx=sx+next[i][0];ty=sy+next[i][1];if(map[tx][ty]==1||map[tx][ty]==3)//如果下一个位置是1或者是已经被标记过的圈外0continue;if(tx<0||tx>n+1||ty<0||ty>n+1)continue;map[tx][ty]=3;//满足上述条件，证明是圈外零，所以赋为3dfs(tx,ty,n);}}
int main()
{int n;do{scanf("%d",&n);}while(n<1||n>30);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);dfs(0,0,n);//这里不一定要从（0，0）开始，在最外圈0中的任何一个位置开始搜索都可以for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){     if(map[i][j]==3)map[i][j]=0;//将圈外0赋回原来的值else if(map[i][j]==0)map[i][j]=2;//将圈内0赋为2}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",map[i][j]);printf("\n");}return 0;}

考前临时抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s_1,s_2,s_3,s_4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A_1,A_2,\ldots,A_{s_1}A1,A2,…,As1，B_1,B_2,\ldots,B_{s_2}B1,B2,…,Bs2，C_1,C_2,\ldots,C_{s_3}C1,C2,…,Cs3，D_1,D_2,\ldots,D_{s_4}D1,D2,…,Ds4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 55 行数据：第 11 行，为四个正整数 s_1,s_2,s_3,s_4s1,s2,s3,s4。

第 22 行，为 A_1,A_2,\ldots,A_{s_1}A1,A2,…,As1 共 s_1s1 个数，表示第一科习题集每道题目所消耗的时间。

第 33 行，为 B_1,B_2,\ldots,B_{s_2}B1,B2,…,Bs2 共 s_2s2 个数。

第 44 行，为 C_1,C_2,\ldots,C_{s_3}C1,C2,…,Cs3 共 s_3s3 个数。

第 55 行，为 D_1,D_2,\ldots,D_{s_4}D1,D2,…,Ds4 共 s_4s4 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

输入输出样例

输入

输出

思路分析：

这道题目应该采用动态规划dp的思想来解决。我们可以转换成01背包问题。

假设我们看科目a的几道题，总用时为v，但是这里分为左右脑，可以同时做同一科目的两道题，因此两个大脑的用时就都是v/2，因此背包大小就为v/2。假设用左脑的时长为max1，那么另外一半的时长就为v-max1。取左右脑的更大者。

这里的dp数组行为该科目每道题的时长，这里要从小到大排序。列为0到背包的一半价值（即一半的总时长）。如果在该时长下不能完成当前题目（即当前时长小于当前题目的时长），就取上一道题目在该时长下的最大值。如果在该时长下可以完成当前题目的话，就要取max(放入该题目的时长，不放入该题目的时长)，取较大值的原因是这里要考虑实际情况，只有取较大的才能在当前时长内做完当前所有题目。然后最后应该取整个dp中的最大值，就是该脑的情况。

这里采用计算单个科目的时长，最后再累加输出的方法。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int s[100];//每个科目的时长
int a[100];//该科目的各个题目的时长
int b[100];
int c[100];
int d[100];
int v[100];
int dp[2000][2000];
int max(int a,int b)
{if(a>b)return a;else return b;
}
int time(int *a,int length,int v)//三个参数分别为当前需要计算的科目、当前科目的题数、当前科目的总时长
{   int max1=0;sort(a,a+length);//对当前科目中题目的各个时长进行从小到大的排序for(int i=1;i<=length;i++)for(int j=0;j<=v/2;j++){     dp[i][j]=dp[i-1][j];if(j>=a[i])dp[i][j]=max(dp[i-1][j-a[i]]+a[i],dp[i][j]);//如果当前时长比题目的时长要大的话，就取放入该题目和不放入该题目的较大值max1=max(max1,dp[i][j]);}return max(max1,v-max1);//取左右脑的较大值
}
int main()
{  for(int i=0;i<4;i++)scanf("%d",&s[i]);for(int i=1;i<=s[0];i++){scanf("%d",&a[i]);v[0]+=a[i];}for(int i=1;i<=s[1];i++){scanf("%d",&b[i]);v[1]+=b[i];}for(int i=1;i<=s[2];i++){scanf("%d",&c[i]);v[2]+=c[i];}for(int i=1;i<=s[3];i++){scanf("%d",&d[i]);v[3]+=d[i];}int sum=0;sum+=time(a,s[0],v[0])+time(b,s[1],v[1])+time(c,s[2],v[2])+time(d,s[3],v[3]);//将各个科目所需的最短时长加起来printf("%d",sum);return 0;}

PERKET

题目描述

Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 nn 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 ss 和苦度 bb。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。

众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。

输入格式

第一行一个整数 nn，表示可供选用的食材种类数。

接下来 nn 行，每行 22 个整数 s_isi 和 b_ibi，表示第 ii 种食材的酸度和苦度。

输出格式

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

输入输出样例

输入 #1复制

1
3 10

输出 #1复制

输入 #2复制

2
3 8
5 8

输出 #2复制

输入 #3复制

输出 #3复制

说明/提示

数据规模与约定

对于 100\%100% 的数据，有 1 \leq n \leq 101≤n≤10，且将所有可用食材全部使用产生的总酸度和总苦度小于 1 \times 10^91×109，酸度和苦度不同时为 11 和 00。

思路分析：

这道题一开始所采用的方法是暴力枚举，ac了一半，是由于这道题用枚举的话需要考虑的情况太多了。任意的组合都可以，只要是绝对差最小，并且有的可能只需要放一种配料，因此这里还是需要采用dfs的方法。

先定义一个搜索函数，里面有四个参数分别为当前调料的序号、当前的总酸度、当前的总苦度以及当前的绝对差。搜索函数的终止条件是当酸度和苦度都为0时，也就是搜到底了。先判断是否为清水的情况，也就是总酸度为1和总苦度为0。然后判断当前的绝对差是否小于最小的绝对差，如果小于的话就替换掉min的值。

调用搜索函数这里需要两个，分为放当前调料以及不放当前调料，取两者较小的即可。

代码实现：

#include<stdio.h>
#include<math.h>
long long s[1000];//调料酸度
long long b[1000];//调料苦度
long long min=0x7ffff;//题目要求的范围i较大，因此这里min的初值为0x7ffff
long long i,j;
void dfs(long long count,long long sum1,long long sum2,long long sub)//当前的调料序号、当前调料酸度、当前调料苦度、当前的绝对差
{   if(s[count]==0&&b[count]==0){   if(sum1==1&&sum2==0)//判断是否为清水return;min=min<sub?min:sub;return;}else{dfs(count+1,sum1*s[count],sum2+b[count],abs(sum1*s[count]-(sum2+b[count])));//放入当前调料dfs(count+1,sum1,sum2,abs(sum1-sum2));//不放当前调料}}
int main()
{int n;   scanf("%d",&n);for(long long i=0;i<n;i++)scanf("%lld %lld",&s[i],&b[i]);dfs(0,1,0,0);printf("%lld",min);return 0;}

莱克计数

题目描述

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100; 1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式

第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。

输出格式

第1行：农夫约翰田地里的池塘数量。

一行：水坑的数量

输入输出样例

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

思路分析：

这道题主要是搜索中的连通块问题。思路比较简单。在主函数中循环整个地图，遇到水就开始搜索，然后将当前位置以及周围所有的水全部变成旱地，并且此时计数器+1，因为这里斜着也算是相邻的，因此这里的方向函数需要有八组数据，分别是上下左右、左上、右上、左下以及右下。

在搜索函数中，当下一个位置是旱地时，就证明下一位置与当前位置构成不了水坑，同时还需要判断是否越界。以上条件都满足的时候就从下一个位置开始继续搜索。

代码实现：

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
char map1[200][200];
int n,m,sum;
int next1[100][100]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//搜索的八个方向
void dfs(int sx,int sy)//当前位置的行和列
{   int tx,ty;map1[sx][sy]='.';//将当前位置的水变成旱地，以区分不同水坑的中的水for (int i=0;i<8;i++)//从八个方向开始搜索{tx=sx+next1[i][0];ty=sy+next1[i][1];if(map1[tx][ty]=='.')//如果遇到旱地，就证明下一个位置不能与当前位置构成水坑continue;if (tx<0||tx>=n||ty<0||ty>=m)//判断越界continue;dfs(tx,ty);//继续调用搜索函数，从下一个水的位置继续开始搜索}
}
int main()
{scanf("%d %d",&n,&m);for(int i=0;i<n;i++){ scanf("%s",map1[i]);getchar();//因为是字符图形的输入，存在换行，所有需要getchar()}int sum=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(map1[i][j]=='W')//当遇到当前水坑中的任意一个水的时候就开始搜索{   dfs(i,j);sum++;}}printf("%d",sum);return 0;
}

单词方阵

题目描述

给一n \times nn×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 88 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：

输入：8                     输出：qyizhong              *yizhonggydthkjy              gy******nwidghji              n*i*****orbzsfgz              o**z****hhgrhwth              h***h***zzzzzozo              z****o**iwdfrgng              i*****n*yyyygggg              y******g

输入格式

第一行输入一个数nn。(7 \le n \le 1007≤n≤100)。

第二行开始输入n \times nn×n的字母矩阵。

输出格式

突出显示单词的n \times nn×n矩阵。

输入输出样例

输入 #1复制

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

输出 #1复制

*******
*******
*******
*******
*******
*******
*******

输入 #2复制

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

输出 #2复制

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

思路分析：

这道题一眼就可以看出应该运用深度搜索的方法，但这道题跟普通的搜索题不同之处就在于，普通的搜索题从起始点到达终点的路线可以是直线也可以是曲线，但这里由于单词只能是横竖斜的，所以从起点到终点的方向必须是一致的。因为可以斜的，所以这里的方向数组应该定义八组数据。

这里我的思路是设置一个输出数组，将里面全部赋为*，然后在原地图中搜索，把能够组成单词的位置重新赋值即可。

搜索函数的终止条件为，当当前的序号为6，也就是到达了需要判断的最后一个字母时，就判断最后一个字母是否也正确，正确的话就从最后一个字母开始，依次从后往前的把*改为单词的字母，这里采用的方法是，每遇到一个单词起始字母y就开始搜索，然后把每次搜索的方向记录下来，这样的话，无论是到下一个位置，还是回溯赋值的时候，直接加减就可以了。

这里需要注意的是，这里是一个字符串数组的输入，应避免使用gets()，因为该函数存在许多的换行问题。所以应直接使用scanf输入即可，另外还需在每输入一行的时候，执行一次getchar()，原因是防止后一个输入函数接收前一个输入末尾的换行。

代码实现：

#include<stdio.h>
char map[200][200];
char print[200][200];
char word[100]="yizhong";
int tx,ty;//下一个位置的坐标
int nx,ny;//存储变化方向
int next[100][100]={{0,-1},{0,1},{-1,-1},{-1,0},{-1,1},{1,-1},{1,0},{1,1}};//从八个方向开始搜索void dfs(int sx,int sy,int count)//当前位置的行列以及当前所需判断的字母序号{    if(count==6)//判断是否到了末尾字母，由于最开始传进来的是0，所以这里6表示的就是第七个字母{if(map[sx][sy]==word[count]){int n=6;for(int i=count;i>=0;i--){print[sx][sy]=word[i];sx-=nx;sy-=ny;//减去变化的方向，即回到上一个的单词正确位置}return;}}else  if(count==1){for(int i=0;i<8;i++){tx=sx+next[i][0];//记录下一个位置ty=sy+next[i][1];nx=next[i][0];//记录改变的方向ny=next[i][1];if(map[tx][ty]==word[count])//判断下一个位置是否为单词中的字母{dfs(tx+nx,ty+ny,count+1);}}}else{if(map[sx][sy]==word[count])dfs(sx+nx,sy+ny,count+1);}}
int main()
{     int n;scanf("%d",&n);for(int i=0;i<n;i++){  scanf("%s",map[i]);getchar();}for(int i=0;i<n;i++)for(int j=0;j<n;j++)print[i][j]='*';for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(map[i][j]=='y')dfs(i,j,1);//如果碰到单词的第一个字母，就开始搜索}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){printf("%c",print[i][j]);}printf("\n");}return 0;
}

马的遍历

题目描述

有一个 n \times mn×m 的棋盘，在某个点 (x, y)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, yn,m,x,y。

输出格式

一个 n \times mn×m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 55 格，不能到达则输出 -1−1）。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4

思路分析：

做这道题的第一反应使用深度搜索(DFS)，但是深度搜索只能得到可以从起始点出发可以到达哪些点，而题目要求的是从起始点开始到某个点的最小路程。所以这里应该采用广度搜索（BFS),此时到达每个点的步数就是至少要走的步数。

在搜索之前定义一个地图数组用于最后的输出，刚开始全部赋为-1，从起点开始可以到达的地方就赋值相应的步数，没有被赋值的位置就是不能到达的位置，就保留原值-1.

因为是BFS，所以这里定义了一个队列，队列内的元素包括当前位置的行和列（注意这里都是从1开始的）以及当前的步数。初始化的时候头和尾相同证明队列中还没放入元素，然后我们将起点放入队列中，将步数赋为0，因为起点到本身的距离就是0，然后尾结点+1。

根据题意我们得出运动的方向有八个，因为马只能走日字。判断下一个位置是否越界以及走过，如果都没有的话，就将下一个位置放入到队列中，队列的头+1，也就是继续搜索队列中的下一个元素。

特别注意的是，广度搜索的终止条件是看队列是否为空，如果为空的话即代表搜索完毕。所以广度搜索不需要递归调用。

代码实现：

#include<stdio.h>
#include<string.h>
int map[1000][1000];
struct queque//定义一个队列，包括当前位置的行和列以及当前步数
{int x;int y;int step;  
}que[160010];
int n,m,x,y;
int next[100][100]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};//运动的八个方向（马走日字）
int head;
int tail;
void bfs(int sx,int sy)//起点坐标
{   que[head].x=sx;//将第一个位置存储到队列中que[head].y=sy;que[head].step=0;map[sx][sy]=que[head].step;tail++;  int tx,ty;while(head<tail)//当head=tail时，即队列为空，代表搜索完毕{for(int i=0;i<8;i++){tx=que[head].x+next[i][0];ty=que[head].y+next[i][1];if(tx<1||tx>n||ty<1||ty>m)//判断是否越界continue;if(map[tx][ty]!=(-1))//判断是否走过continue;que[tail].x=tx;//将下一个位置存储到队列中que[tail].y=ty;que[tail].step=que[head].step+1;map[tx][ty]=que[tail].step;tail++;}head++;//继续搜索队列中的下一个元素}
}
int main()
{scanf("%d %d %d %d",&n,&m,&x,&y);memset(map,-1,sizeof(map));//将地图中的元素全部赋值为-1bfs(x,y);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%-5d",map[i][j]);printf("\n");} }

陨石雨

题目背景

贝茜听说了一个骇人听闻的消息：一场流星雨即将袭击整个农场，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，贝茜开始担心自己的安全问题。以 Farmer John 牧场中最聪明的奶牛的名誉起誓，她一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。根据预报，一共有 MM 颗流星 (1\leq M\leq50,000)(1≤M≤50,000) 会坠落在农场上，其中第i颗流星会在时刻 T_iTi (0\leq T_i\leq1,000)(0≤Ti≤1,000) 砸在坐标为 (X_i, Y_i)(Xi,Yi) (0\leq X_i\leq 300(0≤Xi≤300，0\leq Y_i\leq300)0≤Yi≤300) 的格子里。流星的力量会将它所在的格子，以及周围 44 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 00 开始行动，它只能在第一象限中，平行于坐标轴行动，每 11 个时刻中，她能移动到相邻的（一般是 44 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 tt 被流星撞击或烧焦，那么贝茜只能在 tt 之前的时刻在这个格子里出现。贝西一开始在(0,0)(0,0)。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 -1−1

。

输入格式

* 第 1 行：单个整数：M

* 2..M+1 行：行 i+1 包含三个空格分隔的整数：Xi、Yi 和 Ti

输出格式

*第1行：Bessie到达安全地点所需的最短时间，如果不可能，则为-1。

输入输出样例

输入 #1复制

输出 #1复制

思路分析：

这道题需要求出到达安全位置所需的最短时间，所以使用BFS，按照队列的顺序依次搜索，遇到搜过的就跳过，没搜过的就往里赋值并存入队列.到达第一个安全位置的时间就是到达安全位置的最短时间.

在搜索之前需要定义一个地图数组来存储每个位置上流星到达的时间以及烧焦的时间.刚开始全部初始化为-1.按照流星的输入顺序来判断当前流星的时间如果早于当前位置上的时间的话,就覆盖,烧焦的部分也是同理.

在搜索的时候也与普通的广搜不同,这里的障碍(流星)是有时间段的,因此每当遇到障碍的时候,只要到达障碍位置的时间早于流星到达的时间,这个位置就可以走.当遇到安全位置就输出.如果当队列中的数据都搜索完了还没到安全位置的话就输出-1代表不能到达安全位置.

代码实现:

#include<stdio.h>
#include<string.h>
struct queue//队列包括当前位置的行和列以及所用的时间
{int x;int y;int time;
}que[160010];
int map[1000][1000];
int next[100][100]={{0,-1},{0,1},{1,0},{-1,0}};//移动的四个方向
int m;
int tx,ty;//下一个位置的行和列
int x,y,t;
int head,tail;
void bfs(int sx,int sy)
{tail++;//初始化队列，将（0，0）放入que[head].x=sx;que[head].y=sy;que[head].time=0;map[sx][sy]=que[head].time;while(head<tail)//队列不为空的时候执行{for(int i=0;i<4;i++){tx=que[head].x+next[i][0];ty=que[head].y+next[i][1];if(tx<0||ty<0)continue;if(map[tx][ty]==(-1))//当到达安全位置的时候，输出的应该是前一个位置的时间+1{printf("%d",que[head].time+1);return;}if(que[head].time+1<map[tx][ty])//判断当前流星的时间是否早于原本的位置的时间{que[tail].x=tx;que[tail].y=ty;que[tail].time=que[head].time+1;map[tx][ty]=que[tail].time;tail++;}}head++;}printf("-1");//如果没有到达安全的位置，就输出-1
}
int main()
{scanf("%d",&m);memset(map,-1,sizeof(map));for(int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&t);if(map[x][y]==(-1)||map[x][y]>t)//如果当前位置为空地或者当前流星的时间早于当前位置上的时间，就直接覆盖map[x][y]=t;for(int j=0;j<4;j++){tx=x+next[j][0];ty=y+next[j][1];if(tx>=0&&ty>=0&&(map[tx][ty]==(-1)||map[tx][ty]>t))//判断烧焦的范围map[tx][ty]=t;}}bfs(0,0);return 0;
}

奇怪的电梯

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第ii层楼(1 \le i \le N)(1≤i≤N)上有一个数字K_i(0 \le K_i \le N)Ki(0≤Ki≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,53,3,1,2,5代表了K_i(K_1=3,K_2=3,…)Ki(K1=3,K2=3,…)，从11楼开始。在11楼，按“上”可以到44楼，按“下”是不起作用的，因为没有-2−2楼。那么，从AA楼到BB楼至少要按几次按钮呢？

输入格式

共二行。

第一行为33个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。

第二行为NN个用空格隔开的非负整数，表示K_iKi。

输出格式

一行，即最少按键次数,若无法到达，则输出-1−1。

输入输出样例

输入 #1复制

5 1 5
3 3 1 2 5

输出 #1复制

思路分析:

这道题目需要求出从起始楼层到目标楼层最少按键次数,因此是个很明显的广度搜索的题目.而且是很容易的广搜,因为这里的搜索方向只有两个,电梯只能向上和向下走.

定义一个地图数组存储到每个楼层所需的按键次数,刚开始全部初始化为-1,将起始楼层放入到队列中的头节点,将按键次数赋值为0.然后按照队列的顺序依次往各个楼层赋值.最后直接输出目标楼层中的按键次数即可.如果为-1的话就代表无法到达 .

代码实现:

#include<stdio.h>
#include<string.h>
struct queue//定义一个队列
{int num;//当前楼层的序号int step;//当前的按键次数
}que[160010];
int map[500];
int n,a,b;
int k[500];//存储各个楼层可以移动的层数
int head,tail;
int left,right;//分别是向下和向上
void bfs(int a)
{   tail++;que[head].num=a;//初始化队列que[head].step=0;map[a]=que[head].step;while(head<tail)//队列不为空的情况下执行{   left=que[head].num-k[que[head].num];//存储向上移动到的层数right=que[head].num+k[que[head].num];//存储向下移动到的层数if(right<=n&&map[right]==(-1))//判断是否越界和已经走过{que[tail].num=right;que[tail].step=que[head].step+1;//按键次数等于当前楼层的按键次数+1map[right]=que[tail].step;tail++;}if(left>0&&map[left]==(-1)){que[tail].num=left;que[tail].step=que[head].step+1;map[left]=que[tail].step;tail++;}head++;//继续搜索队列中的下一个}}
int main()
{scanf("%d %d %d",&n,&a,&b);for(int i=1;i<=n;i++)scanf("%d",&k[i]);memset(map,-1,sizeof(map));//将所有楼层按键次数全部赋值为-1bfs(a);printf("%d",map[b]);return 0;}

玉米迷宫

题目描述

去年秋天，奶牛们去参观了一个玉米迷宫，迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用：一头奶牛可以从这个装置的起点立即到此装置的终点，同时也可以从终点出发，到达这个装置的起点。如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。

玉米迷宫的外部完全被玉米田包围，除了唯一的一个出口。

这个迷宫可以表示为N×M的矩阵(2 ≤ N ≤ 300; 2 ≤ M ≤ 300)，矩阵中的每个元素都由以下项目中的一项组成：

 玉米，这些格子是不可以通过的。

 草地，可以简单的通过。

 一个装置的结点，可以将一头奶牛传送到相对应的另一个结点。

 出口

奶牛仅可以在相邻两个格子之间移动，要在这两个格子不是由玉米组成的前提下才可以移动。奶牛能在一格草地上可能存在的四个相邻的格子移动。从草地移动到相邻的一个格子需要花费一个单位的时间，从装置的一个结点到另一个结点需要花费0个单位时间。

被填充为玉米的格子用“#”表示，草地用“.”表示，每一对装置的结点由相同的大写字母组成“A-Z”，且没有两个不同装置的结点用同一个字母表示，出口用“=”表示。

Bessie在这个迷宫中迷路了，她知道她在矩阵中的位置，将Bessie所在的那一块草地用“@”表示。求出Bessie需要移动到出口处的最短时间。

例如以下矩阵，N=5，M=6：

###=##
#.W.##
#.####
#.@W##
######

唯一的一个装置的结点用大写字母W表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费0个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了3个单位时间。

输入格式

第一行：两个用空格隔开的整数N和M；

第2-N+1行：第i+1行描述了迷宫中的第i行的情况（共有M个字符，每个字符中间没有空格。）

输出格式

一个整数，表示Bessie到达终点所需的最短时间。

输入输出样例

输入 #1复制

5 6
###=##
#.W.##
#.####
#.@W##
######

输出 #1复制

思路分析:

这道题是一道普通的bfs题目,只不过添加了传送门的概念,因此只需要在遇到传送门的时候,定义一个查找函数,寻找传送到的位置,然后替换即可,并且时间不变.

在搜索函数中判断当前位置是否为传送门,如果是的话就直接调用查找函数,在查找函数中,循环遍历整个地图,如果碰到与入口传送门相同的字母并且不与入口传送门的坐标相同的话,就证明该位置是传送门的出口,利用指针的方法,直接改变之前的坐标即可.

代码实现:

#include<stdio.h>
char map[500][500];
int sx,sy;
int book[500][500];
int n,m;
int head,tail;
int next[100][100]= {{-1,0},{1,0},{0,-1},{0,1}};//搜索的四个方向
struct queue//当前位置的坐标和时间
{int x;int y;int time;
} que[160010];
int check(int *x,int *y)
{for(int i=0; i<n; i++)for(int j=0; j<m; j++)if((map[i][j]==map[*x][*y])&&(i!=*x||j!=*y))//如果当前位置等于传送门的字母，并且不与传送门入口重合{*x=i;//利用指针直接赋值*y=j;return 0;}}
void bfs(int sx,int sy)
{   book[sx][sy]=1;que[head].x=sx;que[head].y=sy;que[head].time=0;tail++;while(head<tail){if(map[que[head].x][que[head].y]>='A'&&map[que[head].x][que[head].y]<='Z')//判断当前位置是否为传送门{check(&que[head].x,&que[head].y);}if(map[que[head].x][que[head].y]=='=')//判断是否为出口{printf("%d",que[head].time);return;}for(int i=0; i<4; i++){int tx=que[head].x+next[i][0];int ty=que[head].y+next[i][1];if(map[tx][ty]!='#'&&book[tx][ty]==0)//如果下一个位置不是玉米并且没有走过的话，就证明是可以走的{book[tx][ty]=1;que[tail].x=tx;que[tail].y=ty;que[tail].time=que[head].time+1;tail++;}}head++;}}
int main()
{char s;scanf("%d%d",&n,&m);getchar();for(int i=0; i<n; i++){for(int j=0; j<m; j++){scanf("%c",&map[i][j]);if(map[i][j]=='@')//记录起点坐标{sx=i;sy=j;}}getchar();}bfs(sx,sy);return 0;
}

单词接龙

题目背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 nn 表示单词数，以下 nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

输入输出样例

输入 #1复制

5
at
touch
cheat
choose
tact
a

输出 #1复制

说明/提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

n \le 20n≤20

思路分析:

这道题可以运用类似于全排列的思想.先遍历所有单词,找到哪个单词的首字母等于龙头字母,就把其当成龙头单词,此时该单词的使用次数+1,然后开始调用函数.注意调用完函数之后需要回溯,也就是说当前单词不一定就是最长的龙的首单词,因此需要再把当前单词的使用次数-1.

注意,这里子函数中没有把每一个连接好的龙完整的放在一个字符串数组中,而是只保留了龙的最后一个单词以及整条龙的长度,因为当一个新单词要与龙连接的时候,不能与龙的最后一个单词相重合,所以只需看龙的最后一个单词即可.

在子函数中循环更新最大的长度,循环所有的单词,如果该单词的使用次数小于2并且与龙的最后一个单词有重合部分的话,就把它连接起来.

寻找两个字符串重合的子函数中,第一个是龙的末尾单词,第二个是需要判断是否能够连接的单词.判断的方式就是,从龙尾单词的最后一个字母与需要判断的单词的第一个字母开始判断,因为如果连最后一个单词都不能重合的话,前面的字母也就没有判断的必要了.如果有重合的部分就直接返回重合的长度,没有的话就直接返回0.

要注意这里判断字符串的时候为啥不能从头开始比较,因为首先如果要从开始比较的话只能从龙尾单词的第二个字母开始比较(不能完全重合),然后就是有一种特殊情况例如字符串abcbc和bck的话,应该是只有末尾的bc相重合,但是如果从头开始比较的话,就会出错.这里是非常容易出错的地方.

代码实现:

#include<stdio.h>
#include<string.h>
int book[100];//用来标记每个单词使用的次数
int n;
char s[100][100];//接收待连接的单词
char head[100];//接收龙头字母
int maxlength;//龙的最大长度
int relength;//两个字符串的重合长度
int czlength(char *s1,char *s2)//该函数返回两个字符串的重合长度
{int length;length=strlen(s1)<strlen(s2)?strlen(s1):strlen(s2);int i,j;for(i=1;i<length;i++)//因为不能完全重合，所以只要循环到较小字符串的长度-1即可{for(j=0;j<i;j++)if(s1[strlen(s1)-i+j]!=s2[j])break;if(i==j)return i;}return 0; 
}
void dfs(char *s1,int length)//当前龙尾单词和龙的总长度
{    maxlength=maxlength>length?maxlength:length;for(int i=0;i<n;i++){if(book[i]<2){relength=czlength(s1,s[i]);if(relength>0){    book[i]++;dfs(s[i],length+strlen(s[i])-relength);//将当前单词连接到龙尾book[i]--;//回溯部分}}}
}
int main()
{scanf("%d",&n);getchar();for(int i=0;i<n;i++){scanf("%s",s[i]);getchar();}scanf("%s",head);for(int i=0;i<n;i++){if(s[i][0]==head[0])//如果当前单词的首字母等于龙头字母的话，就把当前单词当成龙头单词开始循环{book[i]++;dfs(s[i],strlen(s[i]));//因为刚开始龙中只有龙头单词，因为龙的长度就是龙头单词的长度book[i]--;//回溯部分，继续寻找看有没有下一个满足条件的龙头单词}}printf("%d",maxlength);return 0;}

这篇关于（洛谷）第一个题组题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！