搜索1
一、正方形
题目描述
有n个木棒，需要用上所有木棒，围成一个正方形，如果可以围成正方形，则输出"yes", 否则输出"no"。
输入
第一行输入一个整数T表示样例个数。
对于每个样例，第一行输入一个整数N表示木棍的个数，第二行输入N个数字表示木棒的长度。
输出
对于每个样例，如果可以则输出"yes", 否则输出"no"。
样例输入
3
4
1 1 1 1
5
10 20 30 40 50
8
1 7 2 6 4 4 3 5
样例输出
yes
no
yes
提示
N <= 20
题目分析
本题思路在于先求边长，如果不能整除或者边数小于4都直接输出no，其他情况使用dfs深度优先搜索，当所有的边都被遍历过而且每条边都被使用时输出yes，所以这个就可以作为dfs的结束条件。在dfs内部，先设定一个pick数组，记录这条边是否被选择过。用t记录边长，当遍历到一条边时，先用t减去这条边的边长，如果t小于0，就代表不合适，返回上一个递归，如果等于零，就代表正好，可以直接进行下一次的递归，而当t还大于零的时候，就需要继续减去下一个边长，以此类推，直到搜索结束。（注意外层循环）
#include <bits/stdc++.h>
using namespace std;
int m, n, bc;
int a[21];
bool dfs(int now, int cnt)
{
if (now == m || cnt == m) {//如果已经把所有的边都遍历或者每条边都被使用
if (now == m && cnt == m)//如果两个都符合
return true;//返回true
else return false;//否则返回false
}
int pick[21];
memset(pick, 0, sizeof(pick));
int t = bc;
for (int i = now + 1; i <= m; i++) {
if (pick[i] == 0) {//如果这条边没被用过，就用这条边
pick[i] = 1;//代表这条边已经被使用
t -= a[i];//现在的t代表还需要的边长
if (t == 0) {//如果还需要的边长等于0，代表已经形成了一条边
cnt++;//形成的边数加1
return dfs(i, cnt);//递归
}
else if (t < 0) {//如果这条边的长度大于边长
pick[i] = 0;//代表这条边重新恢复没被用的状态
return dfs(i - 1, cnt);//递归i-1条边
}
}
}
return true;
}
int main()
{
cin >> n;
while (n--)
{
cin >> m;
int sum = 0;
for (int i = 1; i <= m; i++) {
cin >> a[i];//输入每条边的长度
sum += a[i];//sum就是所有边长度的和
}
if (m < 4) {//如果边数小于4，一定不能形成正方形
cout << "no" << endl;//输出no
break;
}
if (sum % 4 != 0) {//如果sum不是4的倍数，即不能整除，不能形成正方形
cout << "no" << endl;//输出no
continue;
}
bc = sum / 4;//bc就是边长
sort(a + 1, a + m + 1);//把所有的边按从小到大的顺序排序
if (dfs(0, 0))//从a[0]，使用的边数是零开始递归，如果返回值是1
cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
二、prime circle
题目描述
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
输入
n (0 < n < 20).
(multi test case)
输出
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
样例输入
6
8
样例输出
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
题目分析
本题需要建立一个判断素数的函数，之后使用dfs，遍历2及以后的元素，如果遍历的位置小于等于n，就代表可以继续进行，从1到n找元素（for循环内），如果是素数就让a[i]等于现在的i，往后遍历，如果已经到n，就计算a[n]+a[1]是不是素数，是就输出。不是的话继续遍历，但是先把pick[i]赋值为零，代表没遍历过这个位置。
#include <bits/stdc++.h>
using namespace std;
int a[20], pick[20], n;
int isPrime(int k) {
for (int j = 2; j < k; j++ ) {
if(k % j == 0) return 0;// 如果不为素数返回0
}
return 1;// 反之则返回1
}
void dfs(int pos) {
if (pos > n) {//如果当前元素的序号大于n
if(isPrime(a[n] + a[1])) {//如果最后一个元素加第一个元素是素数
for (int i = 1; i < n; i++)
cout << a[i] << " ";//输出所有的元素
cout << a[n] << endl;
}
}
for (int i = 1; i <= n; i++) {//当当前元素的序号小于等于n时
if (isPrime(i + a[pos - 1]) && pick[i] == 0) {//如果i没遍历过且i+a[pos-1]是素数
a[pos] = i;//a[pos]等于i（这样可以保证加起来都是素数）
pick[i] = 1;//记录已经遍历过这个位置的元素
dfs(pos + 1);//递归下一个位置的元素
pick[i] = 0;//如果pos+1大于n之后就会执行这条语句，从而可以输出所有的情况
} }}
int main() {
int s = 1;
while (cin >> n) {
a[1] = 1;//第一个数是1
pick[1] = 1;//第一个元素已经遍历过
cout << "Case " << s << ":" << endl;
dfs(2);//直接遍历第二个元素
cout << endl;
s++;
}
return 0;}
三、 棋盘问题
题目描述
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
样例输入
2 1
#.
.#
4 4
…#
…#.
.#…
#…
-1 -1
样例输出
2
1
题目分析
本题题意就是在#的地方摆放k个棋子，保证不同行不同列，有几种摆放方式。有一个很巧妙的方式，就是用a[p][j]表示第p行j列的元素，用pick[j]表示第j列是否已经摆放过棋子，这样行和列一起只能遍历一次，非常巧妙。之后就是使用dfs算法，如果已经摆好了k个棋子就把输出的结果++，之后return。如果某一行的第j列是#而且这一列没有别的元素被遍历过，就把棋子放在这个地方，以此类推。
#include <bits/stdc++.h>
using namespace std;
int m, n, cot, pick[10];
char a[10][10];
void dfs(int p, int k) {//p代表行，k代表摆好的棋子
if (k == n) {//如果已经摆放好了k个棋子就给输出的结果加1并且返回
cot++; return;
}
if (p >= m) return;//如果已经遍历到了大于m的行
for (int j = 0; j < m; j++) {
if (a[p][j] == '#' && pick[j] == 0) {//如果这个地方为#且这一列没放过棋子
pick[j] = 1;//记录已经遍历过这列
dfs(p + 1, k + 1);//递归下一行元素，同时有摆好的棋子数加1
pick[j] = 0;//如果下一行的元素满足k=n，就会返回这个，回溯
}
}
dfs(p + 1, k);//递归下一行的元素，但是这一行没有摆放棋子
return;
}
int main() {
while (true) {
cin >> m >> n;
if (m == -1 && n == -1) break;//如果输入是-1-1就结束
cot = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];//输入棋盘的分布
dfs(0, 0);//从00开始遍历
cout << cot << endl;
}
return 0;
}
四、非常可乐
题目描述
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
输入
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
输出
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
样例输入
7 4 3
4 1 3
0 0 0
样例输出
NO
3
题目分析
本题采用了数论的思路，先使得m比n大，之后求出二者的最大公约数，之后判断能不能平分，如果不能直接输出no，如果可以就输出可乐总体积除以最大公约数再减1.
#include <bits/stdc++.h>
using namespace std;
int s, n, m, cn;
int main()
{
while (cin >> s >> n >> m)
{
if (s == 0 && n == 0 && m == 0) break;
if (n > m) {//使m比n大
int t = m;
m = n;
n = t;
}
int tmp = __gcd(n, m);//求nm的最大公约数
if (s / tmp % 2 != 0)/*如果可乐的体积除以最大公约数关于2的余数不等于零，也就是说没有办法平分*/
cout << "NO" << endl;
else//否则就可以平分
cout << s / tmp - 1 << endl;/*s/tmp是需要倒在大瓶子里的次数，但是由于最后有一半要去小瓶子里，所以减1*/
}
return 0;
}
五、迷宫问题
题目描述
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
题目分析
01迷宫，0代表可以走的路，从00开始找出唯一的一条路到55。本题采用dfs算法，首先使用一个dfs遍历走出一条路，在走到终点的时候，判断mi是否被更新，如果没有被更新就更新为step并且返回。之后再使用另一个dfs进行遍历，如果在第一个dfs中已经走过出口而且已经更新了mi值而且没输出过就输出。注意在这个dfs里面把每一步的xy值都存在了两个数组里面。（为什么一定要写两个dfs呢？——在第一个dfs里面已经确定了一个路径并且把mi更新为这条路径需要的step数，也就是最短路径所需要走的步数，第二个dfs需要保证走的也是最短路径）
#include <bits/stdc++.h>
using namespace std;
int a[10][10], visit[10][10], b[25], c[25];
int ext[4][2] = {1,0, -1,0, 0,-1, 0,1};//代表右左下上四个方向
int mi = 99999999, flag = 0;
void dfs1(int x, int y, int step)
{
int tx, ty;//代表现在的坐标
if(x == 4 && y == 4) {//如果已经到达出口
if(mi > step)//如果mi没有被更新
mi = step;//就把mi更新为step
return ;
}
for (int k = 0; k < 4; k++) {//四个方向依次看是否符合条件
tx = x + ext[k][0];//向右左下上四个方向移动
ty = y + ext[k][1];
if(tx < 0 || ty < 0 || tx > 4 || ty > 4)//保证还在迷宫里面
continue;
if (visit [tx][ty] == 0 && a[tx][ty] == 0) {//如果没走过这个位置且这个位置不是墙
visit[tx][ty] = 1;//走这个位置
dfs1(tx, ty, step + 1);//递归现在位置的四个方向，走过的路径++
visit[tx][ty] = 0;//回溯，恢复到没走过这个位置的时候
}
}
}
void dfs2(int x, int y, int step)
{
int tx, ty;//代表现在的位置
if(x == 4 && y == 4) { //如果到达出口
if(step == mi && flag == 0) {//如果在dfs1里面已经走到过出口而且没输出过
flag = 1;//代表已经输出
for(int i = 0; i < mi; i++)//输出所有的路径
printf("(%d, %d)\n",b[i],c[i]);
}
return ;
}
for(int k = 0; k < 4; k++) {
tx = x + ext[k][0];//下一个位置的坐标
ty = y + ext[k][1];
if(tx < 0 || ty < 0 || tx > 4 || ty > 4)//保证在迷宫里面
continue;
if (visit[tx][ty] == 0 && a[tx][ty] == 0) {//如果没走过这个位置而且这个位置不是墙
visit[tx][ty] = 1;//记录已经走过了这个位置
b[step] = tx;//数组b就是记录路径中的x值
c[step] = ty;//数组c就是记录路径中的y值
dfs2(tx, ty, step + 1);//递归走下一步
visit[tx][ty] = 0;//回溯，没走过这个位置
}
}
}
int main()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++) {
cin >> a[i][j];
visit[i][j] = 0;
}
visit[0][0] = 1;//已经走过了00
dfs1(0, 0, 1);//首先先走出迷宫
dfs2(0, 0, 1);//输出路径
return 0;
}
六、Catch That Cow
题目描述
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
- Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
- Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
输入
multi test case.
For each test case, contains two space-separated integers: N and K
输出
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
样例输入
5 17
6 18
样例输出
4
4
提示
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
*题目分析
本题采用的思路是把所有的情况也就是±三种情况全部都压在栈中，之后会对每一个栈顶元素进行弹栈操作，之后会对这三个栈顶元素进行分别的3个移动，以此类推，直到最后能到达终点，此时得到的就是最近的路径。
#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int N = 1000000;
int mape[N+10];
int n, k;//n代表七点起点，k代表终点
struct node {
int x, step;
};
int check(int x) {
If (x < 0 || x >= N || mape[x])//如果x不符合条件或者已经走过这个位置
return 0;
return 1;
}
int bfs(int x)
{
int i;
queue<node> Q;
node a, next;
a.x = x;//也就是起点
a.step = 0;//现在初始的步数是0
mape[x] = 1;//记录已经走过这个点
Q.push(a);//把a入队Q
while(!Q.empty()) {//当Q不空时
a = Q.front();//a等于队头
Q.pop();//把队头弹栈
if(a.x == k)//如果现在的位置就是终点的位置
return a.step;//返回步数
next = a;//下一个就是a
//每次都将三种状况加入队列之中
next.x = a.x+1;//下一个的位置是x+1
if(check(next.x)) {//如果接下来的位置符合条件
next.step = a.step+1;//步数加1
mape[next.x] = 1;//记录已经走过这个位置
Q.push(next);//弹入next
}
next.x = a.x-1;//这个和上面一样，位置是x-1
if(check(next.x)) {
next.step = a.step+1;
mape[next.x] = 1;
Q.push(next);
}
next.x = a.x * 2;//位置变成x*2
if(check(next.x)) {
next.step = a.step+1;
mape[next.x] = 1;
Q.push(next);
}
}
return -1;
}
int main()
{
int ans;
while(~scanf("%d%d", &n, &k)) {
memset(mape, 0, sizeof(mape));
ans = bfs(n);
cout << ans << endl;
}
return 0;
}
八、Find a way
题目描述
Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
输入
The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
输出
For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
样例输入
4 4
Y.#@
…
.#…
@…M
4 4
Y.#@
…
.#…
@#.M
5 5
Y…@.
.#…
.#…
@…M.
#…#
样例输出
66
88
66
题目分析
本题使用2次bfs，从而得到两个人到KFC的最短距离，由于kfc不止1个，所以使用数组step记录到i行j列的kfc需要走的步数，最后计算出来之后，使用两个for循环在ans和两个step的和中取最小值，这样就可以得到最少的步数，最后输出ans即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int INF = 0x3f3f3f3f;
char s[maxn][maxn];
int disx[] = {1,0,0,-1};
int disy[] = {0,1,-1,0};//代表右上下左四个走法
int n, m, vis[maxn][maxn], step[maxn][maxn][2];
void bfs(int x, int y, int flag)
{
memset(vis, 0, sizeof(vis));//初始化数组
queue<pair<int,int> >q;
map<pair<int,int>,int>mp;
q.push({x,y});//（x，y）进入队列
vis[x][y] = 1;//记录xy已经走过
mp[{x,y}] = 0;//
while(!q.empty()) {//当队列不空的时候
pair<int,int>t = q.front();//t就等于队首元素
q.pop();//弹出队首元素
if(s[t.first][t.second] == '@')//如果队首元素是KFC
step[t.first][t.second][flag] = mp[{t.first,t.second}];//某个人到这的步数就是mp[{t.first,t.second}]
for(int i = 0; i < 4; i++) {//对于四个方向进行遍历
int fx = t.first + disx[i];
int fy = t.second + disy[i];//更新位置
if(fx >= 0 && fx < n && fy >= 0 && fy < m && s[fx][fy] != '#' && !vis[fx][fy])
{//如果没走出范围而且这个位置能走而且这个位置没走过
vis[fx][fy] = 1;//走这个位置
mp[{fx,fy}] = mp[{t.first,t.second}] + 1;//这个位置的步数++
q.push({fx,fy});//现在的这个位置入队
}
}
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
int yx, yy, mx, my;//第一个人的坐标和第二个人的坐标
for(int i = 0; i < n; i++)
scanf("%s",s[i]);//输入路况
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(s[i][j] == 'Y') {//找到Y的位置并且记录
yx = i;
yy = j;
}
else if(s[i][j]=='M') {//找到M的位置并且记录
mx = i;
my = j;
}
}
}
for (int i = 0; i < n; i++) {//把两个人到ij的时长初始化为极大值
for (int j = 0; j < m; j++) {
step[i][j][0] = INF;
step[i][j][1] = INF;
}
}
bfs(yx, yy, 0);//两次bfs分别计算到KFC的步数
bfs(mx, my, 1);
int ans = INF;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == '@') {//如果是KFC
ans = min(ans, step[i][j][0] + step[i][j][1]);
}//答案就等于ans和两个步数的和的最小值
}
}
printf("%d\n",ans*11);//输出答案
}
return 0;
}