本文介绍了ZUST程序设计算法竞赛中的五个经典题目，包括奇怪的电梯问题、A计划、N皇后问题、数独杀手和石油沉积问题。每个题目都提供了问题描述、解题思路及示例代码，旨在帮助参赛者理解和解决算法竞赛中的实际问题。
ZUST- 程序设计算法竞赛基础【3】
1001.A strange lift
题目：
Problem Description
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button “UP” , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button “DOWN” , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can’t go up high than N,and can’t go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button “UP”, and you’ll go up to the 4 th floor,and if you press the button “DOWN”, the lift can’t do it, because it can’t go down to the -2 th floor,as you know ,the -2 th floor isn’t exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button “UP” or “DOWN”?
Input
The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,…kn.
A single 0 indicate the end of the input.
Output
For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can’t reach floor B,printf “-1”.
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3
题目原址
解题思路：利用bfs 广度优先搜索
代码：
#include<bits/stdc++.h>//万能头文件，包含c++中所有文件
using namespace std;
int N,Start,End;
int a[202];//ki
int vis[202];//标记，1为到过，0为没到过
struct pos
{
int level;//第几层
int steps;//按了几次
};
void bfs();
int main()
{
while(scanf("%d",&N)==1)
{
if(N==0)
{
break;
}
scanf("%d%d",&Start,&End);
for(int i = 1;i <= N;i++)
{
scanf("%d",&a[i]);
vis[i]=0;
}
bfs();
}
return 0;
}
void bfs()
{
pos cur,nex;
cur.level=Start;
cur.steps=0;
queue<pos>qu;//生成一个队列；
qu.push(cur);//将cur加入队列
vis[Start] = 1;
while(!qu.empty())//队列不为空
{
cur = qu.front();//访问首元素
qu.pop();//删除第一个元素
if(cur.level == End)
{
printf("%d\n",cur.steps);
return;
}
nex.level=cur.level+a[cur.level];//下一站，情况一：i+ki；
nex.steps=cur.steps+1;;
if(nex.level <= N)
{
if(vis[nex.level]==0)//没去过
{
vis[nex.level] = 1;//标记
qu.push(nex);//添加元素
}
}
nex.level = cur.level - a[cur.level];//下一站，情况二：i-ki；
nex.steps = cur.steps + 1;
if(nex.level >= 1)
{
if(vis[nex.level] == 0)
{
vis[nex.level] = 1;
qu.push(nex);
}
}
}
printf("-1\n");
return;
}
1002.A计划
题目：
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小NM（1 <= N,M <=10)。T如上所意。接下去的前NM表示迷宫的第一层的布置情况，后NM表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#…
…
****.
…#.
….P
#.…
**…
….
*.#…
Sample Output
YES
题目原址
解题思路：普通深搜，注意在t时间内到达
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,t,xx[4][2]={{1,0},{0,1},{-1,0},{0,-1}},xp,yp,visit[2][11][11]; //xp，yp为终点坐标
char map[2][11][11];
void input(int x)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
visit[x][i][j]=1;//初始化数组，表示没有到过
cin>>map[x][i][j];
if(map[x][i][j]=='P')
{
xp=i;
yp=j;
}
}
}
}
int ABS(int a)
{
return a>0?a:-a;
}
bool dfs(int X,int Y,int Z,int step)
{
int i,j,l,k,x,y,z;
if(map[Z][X][Y]=='P') return 1;//先判断是否到达 ，到达则返回1
if(step==0) return 0;// 再判断时间，看是否超时，超时则返回0
x=ABS(X-xp)+ABS(Y-yp);
if(x>step) return 0;//判断最近理想路程是否超过时间，超过则返回0
for(i=0;i<4;i++)
{
x=X+xx[i][0];
y=Y+xx[i][1];//分情况上下左右移动
z=Z;
if(x>=0&&y>=0&&x<n&&y<m&&visit[z][x][y]&&map[z][x][y]!='*')//如果没有超出表格，标记为1这一条路没有到达过，不撞墙
{
if(map[z][x][y]=='#') z=1-z;//遇到传送门，到另一层
visit[z][x][y]=0;//标记到达
if(map[z][x][y]!='#'&&map[z][x][y]!='*'&&dfs(x,y,z,step-1)) return 1;//如果不是传送，墙，再次搜索后到达终点，则返回1；
visit[z][x][y]=1;//否则，换另一条路，取消标记
}
}
return 0; //都不行，返回0；
}
int main()
{
int T,i,j,k,l;
cin>>T;
while(T--&&cin>>n>>m>>t)
{
input(0);
input(1);
if(dfs(0,0,0,t)) cout<<"YES"<<endl;//如果返回值为1，则成功
else cout<<"NO"<<endl;//返回值为0，则失败
}
return 0;
}
1003.N皇后问题
题目·：
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
题目原址
解题思路：深搜，第一颗棋子下在第一行，在进行判断，注意提前将数据存入表中，否则会超时。
代码：
#include<cstdio>
#include<cmath>
int qizi[20];//qizi[i]=j表示第i行第j列下有棋
int biao[11];//结果存到表中，不存会超时
int n;
int qingkuang;
bool judge(int hang)
{
for(int i=1;i<hang;i++)//扫之前下过棋的每一行是否有与此次所下棋的位置同列或同对角线的
{
if(qizi[i]==qizi[hang]||abs(hang-i)==abs(qizi[hang]-qizi[i]))//对角线的话，斜率相等
return false;
}
return true;
}
void dfs(int hang)
{
if(hang==n+1) qingkuang++;//比如n=2，然后该第二行下棋了
else
{
for(int j=1;j<=n;j++)//在该行选第几列
{
qizi[hang]=j;
if(judge(hang))
{
dfs(hang+1);//在本行能下棋的话，就接着下下一行的棋
}
}
}
}
void cnt(int n)
{
dfs(1);//从第一行开始下棋
}
int main()
{
for(n=1;n<=10;n++)
{
qingkuang=0;
cnt(n);
biao[n]=qingkuang;
}
int q;
while(scanf("%d",&q)!=EOF)
{
if(q==0)
break;
printf("%d\n",biao[q]);
}
return 0;
}
1004.Sudoku Killer
题目:
Problem Description
自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。
数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。
例题：
答案：
Input
本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。
Output
对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output
7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
解题思路：最好用cin和cout，判断边界，暴力深搜。
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int map[10][10];
int num;//记录有多少个数需要填
struct zb//用来储存坐标
{
int x,y;
} a[100];
int jc(int k,int step)//判断能否深搜的条件
{
int x,y;
for(int i=0;i<9;i++)
{
if(map[a[step].x][i]==k||map[i][a[step].y]==k)//判断这个数所处的行和列有没有出现重复的数
{
return 0;
}
}
x=(a[step].x/3)*3;
y=(a[step].y/3)*3;
for(int i=x;i<x+3;i++)//判断这个数所处的那个小九宫格里面有没有重复的数
{
for(int j=y;j<y+3;j++)
{
if(map[i][j]==k)
{
return 0;
}
}
}
return 1;
}
void dfs(int step)
{
if(step==num)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<8;j++)
{
cout<<map[i][j]<<" ";
}
cout<<map[i][8]<<endl;//直接在这里输出结果，要不然会发生可怕的事
}
return;
}
for(int i=1;i<=9;i++)//试这九个数
{
if(jc(i,step))//判断能否填数
{
map[a[step].x][a[step].y]=i;//如果满足条件就填数
dfs(step+1);//搜索下一个数的填法
map[a[step].x][a[step].y]=0; //还原地图
}
}
return;
}
int main()
{
int q=0;
char s;
while(cin>>s)//输入字符
{
num=0;
if(s=='?')//对第一个字符进行特判
{
a[num].x=0;
a[num].y=0;
num++;
map[0][0]=0;
}
else
{
map[0][0]=s-'0';
}
for(int i=0;i<9;i++)//输入后面的数，并把他们转换成整型，没走过的用0代替
{
for(int j=0;j<9;j++)
{
if(i==0&&j==0) continue;
cin>>s;
if(s=='?')
{
a[num].x=i;
a[num].y=j;
num++;
map[i][j]=0;
}
else
{
map[i][j]=s-'0';
}
}
}
if(q++)//用来换行
{
cout<<endl;
}
dfs(0);//从0开始
}
return 0;
}
1005.Oil Deposits
题目：
Problem Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
Sample Output
0
1
2
2
题目原址
解题思路：DFS求连通块
代码：
#include<cstdio>
#include<cstring>
const int maxn = 100 + 5;
char pic[maxn][maxn];
int m,n,idx[maxn][maxn];//标记
void dfs(int r, int c, int id)
{
if(r < 0 || r >= m || c < 0 || c >= n) return;
if(idx[r][c] > 0 || pic[r][c] != '@') return;
idx[r][c] = id;//标记是第几条
for(int dr = -1; dr <= 1; dr++)
{
for(int dc = -1; dc <= 1; dc++)
{
if(dr != 0 || dc != 0) dfs(r+dr,c+dc,id);
}
}
}
int main()
{
while(scanf("%d%d", &m, &n) == 2 && m && n)
{
for(int i = 0; i < m; i++)
{
scanf("%s",pic[i]);
}
memset(idx, 0, sizeof(idx));//都赋值为零
int cnt = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i,j,++cnt);//直接带入cnt+1；cnt++则是先代入cnt，在+1；
}
}
printf("%d\n",cnt);
}
return 0;
}
扫一扫
1659
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
