注意此处提供了链接
1. 棋盘问题
问题描述
- 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。
- 要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放$k$个棋子的所有可行的摆放方案数目$C$。
输入格式
输入含有多组测试数据.
每组数据的第一行是两个正整数$n,k$，用一个空格隔开，表示了将在一个$n∗n$的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。
随后的$n$行描述了棋盘的形状：每行有$n$个字符，其中#表示棋盘区域，.表示空白区域（数据保证不出现多余的空白行或者空白列）。输出格式
对于每一组数据，给出一行输出，输出摆放的方案数目$C$（数据保证 $C<2^{31}$）。
数据范围
$n \leqslant 8, k \leqslant n$
输入样例
$2$ $1$
#.
.#
$4$ $4$
…#
..#.
.#..
#…
$-1$ $-1$输出样例
$2$
$1$
思路
经典dfs问题.
- 方法一: 枚举每一个元素,时间复杂度为$O(2^{n^2})$.
- 方法二: 枚举每一行(或每一列),时间复杂度为$O(n!)$.
代码
- 方法一 :枚举每一个元素
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 10
using namespace std;
int n,k,res;
char g[MAXN][MAXN];
int row[MAXN],col[MAXN];
void dfs(int x,int y,int cnt)
{
if(y==n+1)
y=1,x++;
if(x==n+1)
{
if(cnt==k)
res++;
return ;
}
if(g[x][y]=='#'&&row[x]==0&&col[y]==0)
{
g[x][y]='.';
row[x]=col[y]=1;
dfs(x,y+1,cnt+1);
g[x][y]='#';//恢复现场
row[x]=col[y]=0;
}
dfs(x,y+1,cnt);//不选(x,y)的元素
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
break;
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
res=0;
//memset(col,0,sizeof(col));
//memset(row,0,sizeof(row));
dfs(1,1,0);
printf("%d\n",res);
}
return 0;
}
- 方法二: 枚举每一行(或每一列).
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 10
using namespace std;
int n,k,res;
char g[MAXN][MAXN];
int col[MAXN];//标记该列是否使用
void dfs(int root,int cnt)
{
if(root==n+1)//所有行都枚举完
{
if(cnt==k)//且使用的次数刚好为k
res++;
return ;
}
for(int i=1;i<=n;i++)
{
if(g[root][i]=='#'&&col[i]==0)
{//该点为棋盘元素,且没被访问过
g[root][i]='.';
col[i]=1;
dfs(root+1,cnt+1);//选当前行,枚举下一行
col[i]=0;//恢复现场
g[root][i]='#';
}
}
dfs(root+1,cnt);//当前行不选
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
if(n==-1&&k==-1)
break;
res=0;
//memset(col,0,sizeof(col));
//此处col可以不用清0,由于dfs会恢复现场使得col数组最终为0
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
dfs(1,0);
printf("%d\n",res);
}
return 0;
}
2. 地牢大师
问题描述
你现在被困在一个三维地牢中，需要找到最快脱离的出路！
地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。
向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。
你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。
请问，你有可能逃脱吗？
如果可以，需要多长时间？输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数$L,R,C$分别表示地牢层数，以及每一层地牢的行数和列数。
接下来是$L$个$R$行$C$列的字符矩阵，用来表示每一层地牢的具体状况。
每个字符用来描述一个地牢单元的具体状况。
其中, 充满岩石障碍的单元格用#表示，不含障碍的空单元格用.表示，你的起始位置用S表示，终点用E表示。
每一个字符矩阵后面都会包含一个空行。
当输入一行为0 0 0时，表示输入终止。输出格式
每组数据输出一个结果，每个结果占一行。
如果能够逃脱地牢，则输出Escaped in X minute(s).，其中$X$为逃脱所需最短时间。
如果不能逃脱地牢，则输出Trapped!。数据范围
$1\leqslant L,R,C \leqslant 100$
输入样例
$3$ $4$ $5$
S….
.###.
.##..
###.######
#####
##.##
##…#####
#####
#.###
####E$1$ $3$ $3$
S##
#E#
###$0$ $0$ $0$
输出样例
Escaped in 11 minute(s).
Trapped!
思路
三维bfs,注意移动方向为上下前后左右$6$个方向.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 110
using namespace std;
int h,n,m;//高(z),长(x),宽(y)
int dir[6][3]={
{1 ,0 ,0 },
{-1 ,0 ,0 },
{0 ,1 ,0 },
{0 ,-1 ,0 },
{0 ,0 ,1 },
{0 ,0 ,-1 }
};
struct node{
int x;
int y;
int z;
int step;
};
node start_,end_;
char g[MAXN][MAXN][MAXN];
int vis[MAXN][MAXN][MAXN];
int bfs()
{
queue<node> q;
q.push(start_);
vis[start_.z][start_.x][start_.y]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.x==end_.x&&temp.y==end_.y&&temp.z==end_.z)
return temp.step;
for(int i=0;i<=5;i++)
{
int dx=temp.x+dir[i][1],dy=temp.y+dir[i][2],dz=temp.z+dir[i][0];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&dz>=1&&dz<=h&&vis[dz][dx][dy]==0&&g[dz][dx][dy]!='#')
{
vis[dz][dx][dy]=1;
q.push({dx,dy,dz,temp.step+1});
}
}
}
return -1;
}
int main()
{
while(scanf("%d %d %d",&h,&n,&m)!=EOF)
{
if(h==0&&n==0&&m==0)
break;
memset(vis,0,sizeof(vis));
for(int k=1;k<=h;k++)
for(int i=1;i<=n;i++)
{
scanf("%s",g[k][i]+1);
for(int j=1;j<=m;j++)
{
if(g[k][i][j]=='S')
start_={i,j,k};
else if(g[k][i][j]=='E')
end_={i,j,k};
}
}
int res=bfs();
if(res==-1)
printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",res);
}
return 0;
}
3. 抓住那头牛
问题描述
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点$N$，牛位于点$K$。
农夫有两种移动方式：
- 从 $X$ 移动到 $X−1$ 或 $X+1$，每次移动花费一分钟;
- 从 $X$ 移动到 $2∗X$，每次移动花费一分钟.
假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？输入格式
共一行，包含两个整数$N$和$K$。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
$0 \leqslant N,K \leqslant 10^5$
输入样例
$5$ $17$
输出样例
$4$
思路
经典bfs,一维搜索,此处可不用判断农夫与牛的位置关系.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 100010
using namespace std;
struct node{
int pos;
int step;
};
node start_,end_;
int vis[MAXN];
int dir[3]={-1,1,2};
int bfs()
{
queue<node> q;
q.push(start_);
vis[start_.pos]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.pos==end_.pos)
return temp.step;
for(int i=0;i<=2;i++)
{
int dx;
if(dir[i]==2)
dx=temp.pos*2;
else dx=temp.pos+dir[i];
if(dx>=0&&dx<=100000&&vis[dx]==0)
{
vis[dx]=1;
q.push({dx,temp.step+1});
}
}
}
return -1;
}
int main()
{
scanf("%d %d",&start_.pos,&end_.pos);
printf("%d\n",bfs());
return 0;
}
4. 翻转
问题描述
给定一个 $M×N$ 的 $01$ 矩阵。
你需要选择其中一些元素，并对选择的元素进行翻转操作。
翻转操作是指将所选元素以及与其上下左右相邻的元素（如果有）进行翻转（$0$ 变 $1$，$1$ 变 $0$）。
我们希望最终矩阵变为一个全 $0$ 矩阵，并且选择进行翻转操作的元素数量尽可能少。
输出最佳翻转方案。输入格式
第一行包含整数 $M,N$。
接下来 $M$ 行，每行包含 $N$ 个整数，每个整数为 $0$ 或 $1$。输出格式
共 $M$ 行，每行包含 $N$ 个整数，其中第 $i$ 行第 $j$ 列的整数，表示第 $i$ 行第 $j$ 列元素的翻转次数。
如果翻转操作次数最少的操作方案不唯一，则输出字典序最小的方案。
如果不存在合理方案，则输出IMPOSSIBLE。数据范围
$1 \leqslant M,N \leqslant 15$
输入样例
$4$ $4$
$1$ $0$ $0$ $1$
$0$ $1$ $1$ $0$
$0$ $1$ $1$ $0$
$1$ $0$ $0$ $1$输出样例
$0$ $0$ $0$ $0$
$1$ $0$ $0$ $1$
$1$ $0$ $0$ $1$
$0$ $0$ $0$ $0$
思路
思想同费解的开关 费解的开关代码
先枚举第一行的所有状态(用二进制表示),然后逐层将当前位置$(x,y)$为$1$的将$(x+1,y)$进行翻转(避免后效性),最后判断最后一行是否均为0,满足条件更新最小翻转次数及翻转情况.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 20
using namespace std;
const int inf=0x3f3f3f3f;
int m,n,cnt,res=inf;
int a[MAXN][MAXN],vis[MAXN][MAXN];
int temp[MAXN][MAXN];//暂存原数组并对它进行修改
int dir[5][2]={{0,0},{-1,0},{0,1},{1,0},{0,-1}};
int b[MAXN][MAXN];
void dfs(int x,int y)
{
for(int i=0;i<=4;i++)
{
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=0&&dx<=m-1&&dy>=0&&dy<=n-1)
temp[dx][dy]^=1;
}
vis[x][y]=1;
}
int main()
{
scanf("%d %d",&m,&n);
for(int i=0;i<=m-1;i++)
for(int j=0;j<=n-1;j++)
scanf("%d",&a[i][j]);
for(int state=0;state<(1<<n);state++)
{
cnt=0;
memset(vis,0,sizeof(vis));
memcpy(temp,a,sizeof(temp));
for(int i=0;i<=n-1;i++)//将该状态进行翻转
if((state>>i) &1)
dfs(0,i),cnt++;
for(int i=0;i<=m-2;i++)
for(int j=0;j<=n-1;j++)
if(temp[i][j]==1)
dfs(i+1,j),cnt++;
int flag=1;
for(int i=0;i<=n-1;i++)
if(temp[m-1][i]==1)
{
flag=0;
break;
}
if(cnt<res&&flag==1)
{
res=cnt;
memcpy(b,vis,sizeof(b));
}
}
if(res==inf)
printf("IMPOSSIBLE\n");
else
{
for(int i=0;i<=m-1;i++)
{
for(int j=0;j<=n-1;j++)
printf("%d ",b[i][j]);
printf("\n");
}
}
return 0;
}
5. 找倍数
问题描述
给定一个正整数$n$，请你找到一个它的非零倍数$m$。
要求$m$中只包含数字$0$或$1$，并且总位数不超过 $100$位。输入格式
输入包含多组测试数据。
每组数据占一行，包含一个正整数$n$。
当输入$n=0$时，表示输入结束。输出格式
每组数据输出一行$m$。
如果方案不唯一，则输出任意合理方案均可。数据范围
$1 \leqslant n \leqslant 200$
输入样例
$2$
$6$
$19$
$0$输出样例
$10$
$100100100100100100$
$111111111111111111$
思路
bfs的思想,初始让$1$放入队列,每次取出队头$x$,判断是否满足$x%n==0$,不满足将$10\times x$和$10 \times x+1$放入队列中.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int n;
ll bfs()
{
queue<ll> q;
q.push(1);
while(q.size()>0)
{
ll temp=q.front();
q.pop();
if(temp%n==0)
return temp;
q.push(temp*10);
q.push(temp*10+1);
}
return -1;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
printf("%lld\n",bfs());
}
return 0;
}
6. 质数路径
问题描述
给定两个四位质数$A$和$B$，你需要通过最少的操作次数将$A$变为$B$。
每次操作只能改变当前数的其中一位数字，并且每次操作过后，当前数必须仍然是一个质数。
例如，将$1033$变为$8179$，最少需要进行$6$次操作，具体操作为：1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179
请计算并输出所需要的最少操作次数。输入格式
第一行包含整数$T$，表示共有$T$组测试数据。
每组数据占一行，包含两个四位质数$A$和$B$。输出格式
每组数据输出一行答案，表示所需最少操作次数。
如果无法做到，则输出Impossible。
经实际测试，不存在无解情况，特此声明。数据范围
$1 \leqslant T \leqslant 100$.
$ 1000 \leqslant A,B \leqslant 9999$,保证$A$和$B$都是质数.输入样例
$3$
$1033$ $8179$
$1373$ $8017$
$1033$ $1033$输出样例
$6$
$7$
$0$
思路
每一个数最多$9\times 4$的变化,利用bfs找出最短路径即可.
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN 10010
using namespace std;
int t,start_,end_;
int primes[MAXN],is_prime[MAXN],cnt;//判断是否为素数
int vis[MAXN];//标记搜索是否使用过
struct node{
int num;
int step;
};
void get_primes(int n)
{//欧拉筛
for(int i=2;i<=n;i++)
{
if(vis[i]==0)
primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
is_prime[primes[j]*i]=1;
if(i%primes[j]==0)
break;
}
}
}
int bfs()
{
queue<node> q;
memset(vis,0,sizeof(vis));
q.push({start_,0});
vis[start_]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.num==end_)
return temp.step;
int x[4]={temp.num/1000,temp.num/100%10,temp.num/10%10,temp.num%10};
//分别存储千位、百位、十位、个位
for(int i=0;i<=3;i++)
{
int tempnum=x[i];//暂存该位
for(int j=0;j<=9;j++)
{
if(tempnum!=j)
{
x[i]=j;//修改该位
int sum=1000*x[0]+100*x[1]+10*x[2]+x[3];
if(is_prime[sum]==0&&vis[sum]==0&&sum>=1000&&sum<=9999)
{
vis[sum]=1;
q.push({sum,temp.step+1});
}
}
}
x[i]=tempnum;//复原该位
}
}
return -1;
}
int main()
{
get_primes(10000);
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&start_,&end_);
printf("%d\n",bfs());
}
return 0;
}
7. 洗牌
问题描述
给定两叠纸牌$S_1$和$S_2$，每叠恰好有$C$张牌。
每张牌的尺寸大小都完全相同，但是颜色可能不同。
下面介绍洗牌规则。
不妨设$S_1$中纸牌从上到下编号依次为 $a_1,a_2,…,a_C$，$S_2$ 中纸牌从上到下编号依次为$b_1,b_2,…,b_C$。
洗牌就是将这两叠牌交错堆叠在一起，形成一个拥有 $2C$张牌的新牌堆$S_{12}$。
新牌堆中的牌由上至下依次为 $a_1,b_1,a_2,b_2,…,a_C,b_C$。
可参考下图：
然后，将牌堆从中间一分为二，下半部分是新的 $S_1$，上半部分是新的 $S_2$。
这样就可以继续进行洗牌操作获得新的$S_{12}$了。
给定$S_1$和$S_2$，请问至少需要进行多少轮洗牌操作方可获得指定牌堆$S_{12}$。输入格式
第一行包含一个整数$T$，表示共有$T$组测试数据。
每组数据第一行包含一个整数$C$。
第二行包含一个长度为$C$的由大写字母构成的字符串，其中第$i$个字母表示初始$S_1$中由底向上第$i$张牌的颜色。
第三行包含一个长度为$C$的由大写字母构成的字符串，其中第$i$个字母表示初始$S_2$中由底向上第$i$张牌的颜色。
第四行包含一个长度为$2C$的由大写字母构成的字符串，其中第$i$个字母表示目标$S_{12}$中由底向上第$i$张牌的颜色。输出格式
共$T$行，每行输出一组数据的结果，首先输出组别编号$i$（从$1$开始），然后输出所需要的最少洗牌次数。如果无法通过洗牌获得目标牌堆，则输出$−1$。
数据范围
$1 \leqslant T \leqslant 1000$,
$1 \leqslant C \leqslant 100$.
卡牌最多有$8$种颜色，用大写字母$A∼H$表示，所以输入字符串中不会出现其他大写字母。输入样例
$2$
$4$
$AHAH$
$HAHA$
$HHAAAAHH$
$3$
$CDE$
$CDE$
$EEDDCC$输出样例
$1$ $2$
$2$ $-1$
思路
此题为模拟+bfs(可不用bfs),最多枚举$2C$次模拟操作,就可以知道能否得到该字符串.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <map>
using namespace std;
int t,n,cas=1;
string s1,s2,res;
void bfs()
{
string temp;
for(int i=0;i<n;i++)
temp+=s2[i],temp+=s1[i];
map<string,int> mp;
queue<string> q;
q.push(temp);
mp[temp]=1;
while(q.size()>0)
{
string t=q.front();
q.pop();
if(t==res)
{
printf("%d %d\n",cas++,mp[t]);
return ;
}
string now;
for(int i=0;i<n;i++)
now+=t[i+n],now+=t[i];
if(mp[now]==0)
{
mp[now]=mp[t]+1;
q.push(now);
}
}
printf("%d -1\n",cas++);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cin >> s1 >> s2 >> res;
bfs();
}
return 0;
}
