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容器来解答，也可以简单的用数组来实现