桂林电子科技大学 ACM 暑假课 | 7 月 25 日 ACM 作业题解

A: 六皇后

题目描述：

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

行号：1 2 3 4 5 6
列号：2 4 6 1 3 5

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

输入：

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

输出：

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

样例输入：

样例输出：

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 之“八皇后”

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

样例输出：

参考程序：

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

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

C:跳马

题目描述：

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

输入：

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

输出：

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

样例输入：

4 8

样例输出：

参考程序：

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

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

D:奇怪的电梯

题目描述：

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

输入：

共二行。

第一行,为 3 个用空格隔开的正整数，表示 N,A,B。
第二行,为 N 个用空格隔开的非负整数，表示 K_i。

输出：

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

样例输入：

1 2	5 1 5 3 3 1 2 5

样例输出：

参考程序：

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