题目链接

专题一 简单搜索

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;
}