脚本宝典收集整理的这篇文章主要介绍了【kuangbin题集】专题一 简单搜索,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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
DFs+状态压缩
把每行的可选列数压缩为一个数,一行一行dfs
,用一个数统计选过的列数,&
运算确定该行可选择的列数~
//dfs,状态压缩
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,res,col;
char a[10];
int b[10];
void dfs(int pos,int chosen)
{
if(pos==n&&chosen==k)res++;
if(pos==n)return ;
if(chosen>k)return ;
dfs(pos+1,chosen);
int x=col&b[pos];
while(x)
{
col-=x&-x;
dfs(pos+1,chosen+1);
col+=x&-x;
x-=x&-x;
}
}
int main()
{
while(scanf("%d%d",&n,&k),n!=-1&&k!=-1)
{
res=0,col=(1<<n)-1;
memset(b,0,sizeof b);
for(int i=0;i<n;i++)
{
scanf("%s",a);
for(int j=0;j<n;j++)
if(a[j]=='#')b[i]+=1<<j;
}
dfs(0,0);
PRintf("%dn",res);
}
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)
bfs
bfs求最短路,可以存下当前最短路的前一个位置,最后从终点逆推到起点~
//bfs求最短路径
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int a[5][5];
bool v[5][5];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int d[5][5];
pair<int,int> last[5][5];
vector<pair<int,int>>res;
void bfs(int sx,int sy)
{
memset(d,0x3f,sizeof d);
queue<pair<int,int>> q;
q.push(make_pair(sx,sy));
v[sx][sy]=true;
d[sx][sy]=0;
while(q.size())
{
pair<int,int> t=q.front();
q.pop();
int x=t.First,y=t.second;
if(x==4&&y==4)return ;
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&nx<=4&&ny>=0&&ny<=4&&!v[nx][ny]&&a[nx][ny]==0)
{
if(d[nx][ny]>d[x][y]+1)
{
d[nx][ny]=d[x][y]+1;
last[nx][ny]=make_pair(x,y);
v[nx][ny]=true;
q.push(make_pair(nx,ny));
}
}
}
}
}
int main()
{
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)scanf("%d",&a[i][j]);
bfs(0,0);
res.push_back(make_pair(4,4));
int x=last[4][4].first,y=last[4][4].second;
while(!(x==0&&y==0))
{
res.push_back(make_pair(x,y));
pair<int,int> t=last[x][y];
x=t.first,y=t.second;
}
res.push_back(make_pair(0,0));
for(int i=res.size()-1;~i;i--)
printf("(%d, %d)n",res[i].first,res[i].second);
return 0;
}
以上是脚本宝典为你收集整理的【kuangbin题集】专题一 简单搜索全部内容,希望文章能够帮你解决【kuangbin题集】专题一 简单搜索所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。