题目链接
A - 棋盘问题
题目描述
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n、 k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1
解题思路
dfs+状态压缩
把每行的可选列数压缩为一个数，一行一行dfs，用一个数统计选过的列数，&运算确定该行可选择的列数~
- 时间复杂度：\((n!)\)
代码
//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("%d\n",res);
}
return 0;
}
J - 迷宫问题
题目描述
定义一个二维数组：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
解题思路
bfs
bfs求最短路，可以存下当前最短路的前一个位置，最后从终点逆推到起点~
- 时间复杂度：\(O(n^2)\)
代码
//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;
}