3.29 题解报告
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
题解
题目大意
电梯每层有一个不同的数字，例如第n层有个数字k，那么这一层只能上k层或下k层，但是不能低于一层或高于n层，给定起点与终点，要求出最少要按几次键
分析
一、搜索：搜索的话用一维的bfs就好，需判断楼层大于0的情况和<n的情况；
二、最短路：构图，将从i层到按动按钮后跳转的楼层，看作连通状态，赋值为1，这样就转换成单源最短路问题；要注意的是，这道题是单向边，我们只要让map里面的值全部为1就可以统计次数了
代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int inf = 1<<30;
int n;
int map[205][205];
int a[205],cnt;
int vis[205],cast[205];
void Dijkstra(int s,int e){
int i,j,min,pos;
memset(vis,0,sizeof(vis));
for(i = 0; i<n; i++)
cast[i] = map[s][i];
cast[s] = 0;
vis[s] = 1;
for(i = 1; i<n; i++){
min = inf;
for(j = 0; j<n; j++){
if(cast[j]<min && !vis[j]){
pos = j;
min = cast[j];
}
}
if(min == inf) break;
vis[pos] = 1;
for(j = 0; j<n; j++){
if(cast[pos]+map[pos][j]<cast[j] && !vis[j])
cast[j] = cast[pos]+map[pos][j];
}
}
}
int main(){
int i,j,s,e,x,y;
while(~scanf("%d",&n),n){
scanf("%d%d",&s,&e);
s--,e--;
for(i = 0; i<n; i++)
for(j = 0; j<n; j++)
map[i][j] = inf;
for(i = 0; i<n; i++){
scanf("%d",&a[i]);
if(i+a[i]<n)
map[i][i+a[i]] = 1;
if(i-a[i]>=0)
map[i][i-a[i]] = 1;
}
Dijkstra(s,e);
printf("%d\n",cast[e]==inf?-1:cast[e]);
}
return 0;
}
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表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#…
…
****.
…#.
….P
#.…
**…
….
*.#…
Sample Output
YES
题解
题目大意
如果遇到一‘#’，则遇到一个传送门，如果它对面也是传送门，那么这个勇士就会在两个门之间无数次地传送下去，不会停下。如果它对面是墙，那么这个勇士要是过去会撞死，如果发现对面已经是被访问过了，那么说明之前有点比这个点更早到达对面，因此一旦遇到传送门并发现对面是这三种情况，我们就直接将这个位置以及他得对面位置赋为‘*’，代表这些位置不能走，其他情况遇到传送门，就将勇士传送到另一层。如果第一个到达公主位置的那条路所经历的时间都比最大时间大的话，则公主就会挂掉，因为以后到达的只会比第一次的时间更长，因此一旦遇到当前位置是结束位置，我就判断当前所用的时间是否超过了限定的时间，如果没有超过，直接输出YES，结束搜索，如果超过了，也直接结束搜索，输出NO，代表不能成功救出公主，公主挂掉。
https://blog.csdn.net/wyxeainn/article/details/52495648
分析
1.退出时的判断条件（找到公主位置，也就是等于P的时候退出）
2.时间的限制，题目中要求骑士要在一定时间内将公主解救出来（if(a.step>=time)
break;时间多于规定时间，就不再进行搜索，退出本次循环（但注意，并非退出bfs()函数））
3.最重要的一点就是克服层次的转化，一开始的时候
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
char map[2][120][120];
int vis[2][120][120],maxx,m,n;
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
struct node {
int x,y,z;
int step;
friend bool operator < (node n1,node n2){
return n1.step>n2.step;
}
}p,temp;
int judge(node s){
if(s.x<0||s.y<0||s.x>=m||s.y>=n)
return 1;
if(map[s.z][s.x][s.y]=='*'||map[s.z][s.x][s.y]=='#')
return 1;
if(vis[s.z][s.x][s.y]||s.step>maxx)
return 1;
return 0;
}
void bfs(){
priority_queue<node>q;
p.x=0;p.y=0;p.z=0;
p.step=0;
vis[0][0][0]=1;
q.push(p);
while(!q.empty()){
p=q.top();
q.pop();
for(int i=0;i<4;i++){
temp.x=p.x+dx[i];
temp.y=p.y+dy[i];
temp.step=p.step+1;
if(map[p.z][temp.x][temp.y]=='#'){
if(p.z) temp.z=0;
else temp.z=1;
}
else temp.z=p.z;
if(judge(temp)){
continue;
}
if(map[temp.z][temp.x][temp.y]=='P'){
printf("YES\n");return ;
}
vis[temp.z][temp.x][temp.y]=1;
q.push(temp);
}
}
printf("NO\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(vis,0,sizeof(vis));
memset(map,'\0',sizeof(map));
scanf("%d%d%d",&m,&n,&maxx);
int i,j,k;
for(i=0;i<2;i++){
for(j=0;j<m;j++)
scanf("%s",map[i][j]);
}
bfs();
}
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
题解
我觉得不可能实现！！！
但是bug被oj忽略了！！！！
所以我很生气，不想写题解！！！！
代码
#include <stdio.h>
#include <cmath>
using namespace std;
const int N=12;
int map[N],cnt;
bool check(int x,int y){
for(int i=1;i<x;i++){
if(map[i]==y||abs(x-i)==abs(map[i]-y))
return false;
}
return true;
}
void dfs(int x,int m){
if(x>m){
++cnt;
return;
}
for(int i=1;i<=m;i++){
if(check(x,i)){
map[x]=i;
dfs(x+1,m);
}
}
return;
}
int main(){
int i,ans[11];
for(i=1;i<11;i++){
cnt=0;
dfs(1,i);
ans[i]=cnt;
}
while(scanf("%d",&i)){
if(i==0)
return 0;
printf("%d\n",ans[i]);
}
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
题解
题目大意
给一个没有完成的数独，输出完整结果。数据保证有且只有一个解。
分析
暴力深搜啊！找到每个空的位置，把1到9尝试一遍只要不冲突就填上再往下搜索一直找到解就行了。
坑！！！
输入输出，最好用cin和cout，如果聪明的你用了getchar()？
真好！掉坑里了，赶紧爬起来继续肝吧！
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int x,y;
}p[1010];
int map[10][10];
int cnt,flag;
bool ok(int k,int t){
for(int i=0;i<9;i++)
if(map[p[t].x][i]==k||map[i][p[t].y]==k)
return false;
int tx=p[t].x/3*3;
int ty=p[t].y/3*3;
for(int i=tx;i<tx+3;i++){
for(int j=ty;j<ty+3;j++){
if(map[i][j]==k)
return false;
}
}
return true;
}
void dfs(int x){
if(x==cnt){
flag=1;
for(int i=0;i<9;i++){
for(int j=0;j<8;j++)
printf("%d ",map[i][j]);
printf("%d\n",map[i][8]);
}
return ;
}
for(int i=1;i<=9;i++){
if(ok(i,x)&&!flag){
map[p[x].x][p[x].y]=i;
dfs(x+1);
map[p[x].x][p[x].y]=0;
}
}
}
int main(){
int v=0;
char s[2];
while(scanf("%s",s)!=EOF){
cnt=0;
memset(map,0,sizeof(map));
if(v) printf("\n");
else v=1;
if(s[0]=='?'){
map[0][0]=0;
p[cnt].x=0;
p[cnt++].y=0;
}
else map[0][0]=s[0]-'0';
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(i==0&&j==0) continue;
scanf("%s",s);
if(s[0]=='?'){
map[i][j]=0;
p[cnt].x=i;
p[cnt++].y=j;
}
else map[i][j]=s[0]-'0';
}
}
flag=0;
dfs(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
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
5 5
****@
@@@
@**@
@@@@
@@**@
0 0
Sample Output
0
1
2
2
题解
题目大意
就是找出有多少块有石油的区域，就是数组中的@,这边相邻指的是是周围的八个位置。
分析
这一题可以说是搜索中最基础的一题之一。挨个点搜索标记就行了。
代码
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int M,N,total;
char map[110][110];
int vs[110][110];
int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8]={ 0, 1, 1, 1, 0,-1,-1, -1};
struct q{
int xx;
int yy;
}q[10100];
void find(int x,int y){
int x1,y1;
int head,tail;
if(!vs[x][y]){
total++;
vs[x][y]=1;
}
if(vs[x][y]==1){
head=0,tail=1;
q[0].xx=x;
q[0].yy=y;
while(tail>head){
x=q[head].xx;
y=q[head].yy;
for(int i=0;i<8;i++){
x1=x+dx[i];y1=y+dy[i];
if(x1>=1&&x1<=M&&y1>=1&&y1<=N)
if(map[x1][y1]=='@'&&!vs[x1][y1]){
q[tail].xx=x1;
q[tail].yy=y1;
vs[x1][y1]=1;
tail+=1;
}
}
head++;
}
}
}
void bfs(){
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
if(map[i][j]=='@'&&!vs[i][j])
find(i,j);
}
int main(){
ios::sync_with_stdio(false);
while(cin>>M>>N){
cin.get();
if(M<=0||N<=0) break;
total=0;
memset(map,0,sizeof(map));
memset(vs,0,sizeof(vs));
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
cin>>map[i][j];
bfs();
cout<<total<<endl;
}
return 0;
}
1006 The Rotation Game
题目
Problem Description
The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.
Initially, the blocks are placed on the board randomly. Your task is to move the blocks so that the eight blocks placed in the center square have the same symbol marked. There is only one type of valid move, which is to rotate one of the four lines, each consisting of seven blocks. That is, six blocks in the line are moved towards the head by one block and the head block is moved to the end of the line. The eight possible moves are marked with capital letters A to H. Figure 1 illustrates two consecutive moves, move A and move C from some initial configuration.
Input
The input consists of no more than 30 test cases. Each test case has only one line that contains 24 numbers, which are the symbols of the blocks in the initial configuration. The rows of blocks are listed from top to bottom. For each row the blocks are listed from left to right. The numbers are separated by spaces. For example, the first test case in the sample input corresponds to the initial configuration in Fig.1. There are no blank lines between cases. There is a line containing a single `0’ after the last test case that ends the input.
Output
For each test case, you must output two lines. The first line contains all the moves needed to reach the final configuration. Each move is a letter, ranging from A' toH’, and there should not be any spaces between the letters in the line. If no moves are needed, output `No moves needed’ instead. In the second line, you must output the symbol of the blocks in the center square after these moves. If there are several possible solutions, you must output the one that uses the least number of moves. If there is still more than one possible solution, you must output the solution that is smallest in dictionary order for the letters of the moves. There is no need to output blank lines between cases.
Sample Input
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0
Sample Output
AC
2
DDHH
2
题解
题目大意
给你一个游戏初始状态（从上到下，从左到右顺序给出），其中包含两个横轴，两个竖轴，你可以进行向上转，向下转，向左转，向右转操作（一次旋转一个横轴或竖轴），你的任务是找到一个最短的操作序列，使中间3*3的方格中只有一种数字（除了中央的那个空方格），如果有多个长度相等的序列，输出字典序最小的那个，如果不需要操作，输出"No moves needed"。然后还要输出中间区域的数字。
数据保证游戏中只有1，2，3这几个数字且每个出现8次。
分析
本题一共有24个格子，状态数即有个C(24,8)C(16,8)=73547112870个,BFS肯定是要MLE的，这个时候就得用迭代加深搜索
1.加上一个估价函数H()=中间8个格子中最多的数字凑成答案的最理想步数剪枝即可。
（当前步数+H()后大于深度限 制,那么无论怎么转也不能在深度限制下凑出答案。）
2.在实现时手工打出8种旋转方案，便于保证字典序。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 7
#define MAXM
#define INF 0x3f3f3f3f
typedef long long int LL;
const int Input_rule[8][8]={
{0,0,0,0,0,0,0,0},
{2,3,5,0,0,0,0,0},
{2,3,5,0,0,0,0,0},
{7,1,2,3,4,5,6,7},
{2,3,5,0,0,0,0,0},
{7,1,2,3,4,5,6,7},
{2,3,5,0,0,0,0,0},
{2,3,5,0,0,0,0,0},
};
const int rule[9][3]={
{0,0,0},
{3,1,0},
{5,1,0},
{3,0,1},
{5,0,1},
{5,1,1},
{3,1,1},
{5,0,0},
{3,0,0},
};
const int back[9]={0,6,5,8,7,2,1,4,3};
const char opp[9]={'0','A','B','C','D','E','F','G','H'};
int map[MAXN+5][MAXN+5];
char road[100];int cnt=0;
int N;
int h(){
int num[5];
memset(num,0,sizeof(num));
for(int i=3;i<=5;++i)
for(int j=3;j<=5;++j)
if(!(i==4&&j==4))++num[map[i][j]];
int Smax=-INF;
for(int i=1;i<=3;++i)
Smax=max(Smax,num[i]);
return 8-Smax;
}
void rotate(int now){
bool CorR=rule[now][1],dir=rule[now][2];
if(CorR){
int col=rule[now][0];
if(dir==0){
for(int i=0;i<N;++i)
map[i][col]=map[i+1][col];
map[N][col]=map[0][col];
map[0][col]=0;
}
else{
for(int i=N+1;i>1;--i)
map[i][col]=map[i-1][col];
map[1][col]=map[N+1][col];
map[N+1][col]=0;
}
}
else{
int row=rule[now][0];
if(dir==0){
for(int i=0;i<N;++i)
map[row][i]=map[row][i+1];
map[row][N]=map[row][0];
map[row][0]=0;
}
else{
for(int i=N+1;i>1;--i)
map[row][i]=map[row][i-1];
map[row][1]=map[row][N+1];
map[row][N+1]=0;
}
}
}
bool dfs(int dep,int &Maxdep){
if(dep+h()>Maxdep)return 0;
if(h()==0)return 1;
for(int i=1;i<9;++i){
rotate(i);
road[++cnt]=opp[i];
if(dfs(dep+1,Maxdep))return 1;
--cnt;
rotate(back[i]);
}
return 0;
}
int main(){
N=7;
int i,j,n;
while(~scanf("%d",&map[1][3])&&map[1][3]){
cnt=0;
n=2;
i=1;
while(i<=N){
j=Input_rule[i][n++];
scanf("%d",&map[i][j]);
if(n>Input_rule[i][0]){
n-=Input_rule[i][0];
++i;
}
}
int ans;
for(ans=0;;++ans)
if(dfs(0,ans))break;
if(ans==0)puts("No moves needed");
else{
for(i=1;i<=cnt;++i)
putchar(road[i]);
puts("");
}
printf("%d\n",map[3][3]);
}
}