抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

1.A:六皇后

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

1.A:六皇后

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。


上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i个数字表示在第i行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入

一行一个正整数 n,6≤n≤13,表示棋盘是 nxn大小的

输出

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

样例输入

6

样例输出

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

参考程序(自己打的)

#include<iostream>
using namespace std;
int count = 0;
int chess[6][6]={0};
int notDanger(int row,int col ){
    int i,k;
    for(i=0;i<6;i++){
        if(chess[i][col]==1)
        return 0;
    }
    for(i=row,k=col;i>=0&&k>=0;i--,k--)
    if(chess[i][k]==1)
    return 0;
    
    for(i=row,k=col;i>=0&&k<6;i--,k++)
    if(chess[i][k]==1)
    return 0;
    
    return 1;
}

void Print(){
    int i,j;
    for(i=0;i<6;i++){
        for(j=0;j<6;j++){
            if(chess[i][j]==1)
            cout<<j+1<<" ";
        }
    }
    cout<<endl;
}
void EightQueen( int row ){
    int col;
    if( row>5 )                       {
        Print();                      
        count++;
        return ;}

题解:写得十分长,但是该有的东西还是有的,比如判断的函数,还有输出以及循环的函数,这里没用到搜索,只是枚举,详细请见ACM之“八皇后”

2.B:东南西北

题目描述

给出起点和终点的坐标及接下来T个时刻的风向(东南西北),每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少步数。

如果无法偏移至终点,输出“-1”。

输入

第一行两个正整数x1,y1,表示小明所在位置。

第二行两个正整数x2,y2,表示小明想去的位置。

第三行一个整数T,表示T个时刻。1<=T<=50

第四至第N+3行,每行一个字符,表示风向,即东南西北的英文单词的首字母

输出

最少走多少步。

样例输入

1 1
2 2
5
E
N
W
W
N

样例输出

2

参考程序

#include <iostream>
using namespace std;
int x,y,x1,y1,n,s=0;
char a;
int l=0;
int main()
{
    cin>>x>>y>>x1>>y1;
    cin>>n;
    if(x==x1&&y==y1){cout<<'0';return 0;}
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(x1-x>0&&a=='E')x++,s++;
        else if(x1-x<0&&a=='W')x--,s++;
        if(y1-y>0&&a=='N')y++,s++;
        else if(y1-y<0&&a=='S')y--,s++;
    }
    if(x==x1&&y==y1)cout<<s;
    else cout<<"-1";
    return 0;
}

题解

只要边输入边看这个方向是不是朝着终点。如果是,就动。否则就不动。

3.C:跳马

题目描述

中国象棋半张棋盘如图 11 所示。马自左下角 (0,0)(0,0) 向右上角 (m,n)(m,n) 跳。规定只能往右跳,不准往左跳。比如图 11 中所示为一种跳行路线,并将路径总数打印出来。

输入

只有一行:两个数 n,m。0<=n,m≤18

输出

输出一个数:马从左下角到右上角的总方案数 total。

样例输入

4 8

样例输出

37

参考程序

#include <stdio.h>
#include <queue>
using namespace std;
int dx[4]= {1, 2, 1, 2};
int dy[4]= {2, 1, -2, -1};//四种走法
int ways=0;//记录路线条数

struct NODE {
    int x, y;
};//记录路线上的点的坐标

bool Valid (NODE h, int m, int n) {
    if ((h.x<=m)&&(h.y>=1)&&(h.y)<=n)
        return 1;
    else
        return 0;
}//判断下的这步棋是否符合规则

bool bfs (NODE s, int m, int n) {
    queue<NODE>q;//建立路线队列
    NODE now, next;//用于记录当前棋和进入下一步的棋
    q.push(s);//起点入列
    while (!q.empty()) {
        now = q.front();
        q.pop();//取出当前棋子并出列
        if ((now.x==m)&&(now.y==n)) {
            ways++;
            continue;
        }//判断是否走到终点
        for ( int i=0; i<4; i++) {
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];//走出四种走法
            if (Valid(next,m, n))
                q.push(next);//如果有效则入列
        }
    }
}

int main() {
    int m, n;
    scanf ("%d %d", &m, &n);
    NODE s;
    s= {1,1};//起点
    bfs (s, n, m);//开始搜索
    printf ("%d\n", ways);
    return 0;
}

题解:

搜索中的经典问题,跟help庞学姐类似

4.D:奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)上有一个数字K(0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,5代表了Ki
(K
1
=3,K
2
=3,…),从11楼开始。在1楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?

输入

共二行。

第一行,为3个用空格隔开的正整数,
表示N,A,B

第二行,为N个用空格隔开的非负整数,
表示K_i

输出

一行,即最少按键次数,若无法到达,则输出−1。

样例输入

5 1 5
3 3 1 2 5

样例输出

3

参考程序

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;  //BFS 实现用队列
    vector<int> v; //保存每层按钮上的数值
    vector<int> f; //到达每层最少的按键次数
    vector<bool> flag;//标记值,表示每层是否被访问过,true代表访问过
    int n;
    int start, end;//开始层和结束层
    int tmp;
    cin >> n >> start >> end;
    v.push_back(0);//方便起见,下标从1开始
    f.push_back(0);
    flag.push_back(false);
    for (int  i = 1; i <= n; i++)
    {
        cin >> tmp;
        v.push_back(tmp);
        if(i == start)
            f.push_back(0);//初始化,start层开始为按0次,其余层为-1次
        else
            f.push_back(-1);
        flag.push_back(false);
    }
    q.push(start);

    while (!q.empty()&& !flag.at(q.front()))//队列不为空,切第q.front()层没有被访问过
    {
        flag.at(q.front()) = true;
        int next = q.front() + v.at(q.front());
        if (next <= n) //上楼
        {
            q.push(next);
            f.at(next) = f.at(q.front()) + 1;//记下到达每层最少的按键次数
            if (next == end) //找到end层,退出while循环
            {
                break;
            }
        }
        next = q.front() - v.at(q.front());
        if (next >= 1)//下楼
        {
            q.push(next);
            f.at(next) = f.at(q.front()) + 1;
            if (next == end)//找到end层,退出while循环
            {
                break;
            }
        }
        q.pop();
    }
    cout << f.at(end) << endl;

    return 0;
}

题解

动态分配内存,采用STL的vector容器来解答,也可以简单的用数组来实现

评论