A - Robot Motion HDU - 1035
A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are
N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)
For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.
Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.
You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.
Input
There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.
Output
For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before it is 1.
Sample Input
3 6 5 NEESWE WWWESS SNWWWW 4 5 1 SESWE EESNW NWEEN EWSEN 0 0
Sample Output
10 step(s) to exit 3 step(s) before a loop of 8 step(s)
题意：
机器人出迷宫 四种英文字母表示四个方向 输入三个数字分别表示迷宫的行、列和机器人起始列数，能够离开则输出步数，不能离开即在迷宫中成环，则输出成环前的步数和在环中的步数。
思路：
简单dfs 详细看代码注释
/*HDU 1035*/
#include
#include
#include
using namespace std;
char s[11][11];// 记录指令
int Map[11][11];// 地图步数
int temp,step,restep,qstep;//状态 记录步数 计算重复步数 计算重复前步数
int n,m,k;
void dfs(int x,int y,int z) //x行 y列 z步数
{
if(x=n||y>=m)//判断边界
{
temp=1;
return;
}
step=z;
if(!temp)
{
if(!Map[x][y])
{
Map[x][y]=z;
if(s[x][y]=='W')
dfs(x,y-1,z+1);
else if(s[x][y]=='E')
dfs(x,y+1,z+1);
else if(s[x][y]=='N')
dfs(x-1,y,z+1);
else if(s[x][y]=='S')
dfs(x+1,y,z+1);
}
else
{
restep=z-Map[x][y];//第二次到达此处的步数 减去第一次到达此处的步数 即环中步数
qstep=Map[x][y]-1;//第一次到达此处的步数-1 即到达此处需要的步数 （成环前步数）
}
}
}
int main()
{
while(cin>>n>>m>>k)
{
if(n==0&&m==0)
break;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>s[i][j];
}
memset(Map,0,sizeof Map);
temp=0;
dfs(0,k-1,1);
if(temp)
cout<<step<<" step(s) to exit"<<endl;
else
cout<<qstep<<" step(s) before a loop of "<<restep<<" step(s)"<<endl;
}
return 0;
}B - 全排列 OpenJ_Bailian - 2748
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。
Input
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。
Output
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：
已知S = s 1s 2...s k , T = t 1t 2...t k，则S < T 等价于，存在p (1 <= p <= k)，使得
s 1 = t 1, s 2 = t 2, ..., s p - 1 = t p - 1, s p < t p成立。
Sample Input
abc
Sample Output
abc acb bac bca cab cba
思路：dfs+回溯
输入字符串，依次对每个字符深搜，将搜索到的字符放入字符数组，深搜过程中标记，深搜结束后回溯。
PS: 有小伙伴直接调用STL里面 next_permutation 函数，也可以解决这道题，但是全排列裸题很少有，不建议这样写。（毕竟是为了练习）
/*OpenJ_Bailian 2748*/
#include
#include
#include
using namespace std;
int flag[10010],num;
char Map[10];
string s;
void bfs(char a)
{
if(num==s.size()-1) //字符数满 输出、结束
{
for(int i=0;i<=num;i++)
{
cout<<Map[i];
}
cout<<endl;
return ;
}
for(int i=0;i<s.size();i++)
{
if(flag[i]==0)
{
num++; //放入字符串的字符的个数
flag[i]=1;//记录
Map[num]=s[i];//放入该字符
bfs(s[i]);
flag[i]=0;//回溯
num--;//回溯
}
}
}
int main()
{
while(cin>>s)
{
for(int i=0; i<s.size(); i++)
{
num=0;
Map[0]=s[i];//按字典序改变字符串头部
flag[i]=1; //标记
bfs(s[i]);
memset(Map,'0',sizeof Map);
memset(flag,0,sizeof flag);
}
}
return 0;
}C - Tempter of the Bone HDU - 1010
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output
NO YES
题意：
小狗出迷宫，必须在规定的那1s到达门口才算成功逃出，走过的路将塌陷最多停留1s,即1s必须走一格。
输入三个数分别为行、列、逃出时的时间（s）。
思路：
bfs+回溯+剪枝（剪枝真的不好想）涉及到奇偶剪枝。
常规dfs，剪枝为难点。第一步剪枝就是判断全都是路的情况给的时间都小于最短到达的时间，就不用搜索判断一下直接输出；第二步奇偶剪枝比较难发现，搜索过程中剩余时间（t-step）减去到达终点的所需时间为奇数时就不可能到达终点。
#include
#include
#include
using namespace std;
char Map[101][101];//地图且记录当前位置时间
int flag;//状态
int Next[4][2]={{1,0},{-1,0},{0,-1},{0,1}};//四个方向
int sx,sy,n,m,ex,ey,t,wall;//sx sy开始位置 ex ey 终点位置 wall墙数 t所给时间
void dfs(int x,int y,int time)
{
if(x==ex&&y==ey&&time==t)//到达终点且时间满足条件 结束
{
flag=1;
return;
}
int k=((t-time)+abs(x-ex)+abs(y-ey));//奇偶剪枝 当前剩余时间（t-step）减去到达终点最短需要的时间
if(k&1||k<0)//第二次剪枝 如果k<0 不能走出迷宫 或者 k为奇数 也不能走出迷宫 直接return
return;
for(int i=0;i<4;i++)
{
int dx=x+Next[i][0];
int dy=y+Next[i][1];
if(dx>=0&&dx=0&&dy<m&&Map[dx][dy]!='X')//判断边界且不为墙
{
Map[dx][dy]='X';
dfs(dx,dy,time+1);
Map[dx][dy]='.';//回溯
}
}
return;
}
int main()
{
while(cin>>n>>m>>t)
{
wall=0;flag=0;
if(n==0&&m==0&&t==0)
break;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>Map[i][j];
if(Map[i][j]=='S')//记录起始位置
{
sx=i,sy=j;
}
if(Map[i][j]=='D')//记录终点位置
{
ex=i,ey=j;
}
if(Map[i][j]=='X')//记录墙数
wall++;
}
}
if(n*m-wall<=t)//第一次剪枝 若除去墙的数量小于等于所给时间则必定无法到达。
{
cout<<"NO"<<endl;
continue;
}
Map[sx][sy]='X';//起始位置改为墙
dfs(sx,sy,0);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}D - 素数环 HDU - 1016
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
Sample Input
6 8
Sample Output
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
题意：给出一个正整数n，按字典序列出从一到n的数列且相邻两项相加为素数。保证第一项为1
思路：类似B题 dfs+回溯
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int temp[21];
int Map[21];
bool su(int x)//判断素数
{
int flag=0;
for(int i=2; i<=sqrt(x); i++)
{
if(x%i==0)
{
flag=1;
break;
}
}
if(flag)
return false;
else
{
return true;
}
}
void dfs(int num)//num统计数量
{
if(num==n&&su(Map[0]+Map[num-1]))//数组放满且首项尾项相加为素数 输出 结束
{
for(int i=0; i<n; i++)
{
if(i==n-1)
{
cout<<Map[i]<<endl;
return;
}
cout<<Map[i]<<" ";
}
}
for(int i=2; i<=n; i++)
{
if(temp[i]==0&&su(i+Map[num-1]))//当该项与上一项相加为素数时 才能放入
{
Map[num]=i;//放入
temp[i]=1;//标记
dfs(num+1);
temp[i]=0;//回溯
}
}
}
int main()
{
Map[0]=1;//第一项为1
int m=1;//输出格式 第m组数据
while(cin>>n)
{
memset(temp,0,sizeof temp);
cout<<"Case "<<m++<<":"<<endl;
dfs(1);
cout<<endl;
}
}E - 抓到那头牛 POJ - 3278
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
- Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
- Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
题意：
给一个起点N一个终点K 每一步可以N+1或N-1或2*N，输出最少步数到达K
思路；
简单bfs
通过队列实现bfs
#include <iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int N,K;
int vis[100010];
struct node
{
int x,steps;
};
node p[100010];
int main()
{
int ans = 0;
while(cin>>N>>K)
{
node a,next;
a.x = N,a.steps = 0;//起始状态
memset(vis,0,sizeof(vis));
vis[N] = 1;//标记 防止重复
queue<node> Q;
Q.push(a);//放入队列
while(!Q.empty())
{
a=Q.front();
if (a.x == K)//达到终点 跳出
{
ans = a.steps;
break;
}
else//模拟三种情况 将对应值放入队列
{
if( a.x*2<=100000 && !vis[a.x*2])
{
next.x = a.x*2;
next.steps = a.steps +1;
vis[a.x*2] = 1;
Q.push(next);
}
if ( a.x+1<=100000 &&!vis[a.x+1] )
{
next.x = a.x+1;
next.steps = a.steps+1;
vis[a.x+1] = 1;
Q.push(next);
}
if ( a.x-1>=0 && !vis[a.x-1])
{
next.x = a.x-1;
next.steps = a.steps+1;
vis[a.x-1] = 1;
Q.push(next);
}
Q.pop();
}
}
printf("%d\n",ans);
}
return 0;
}F - Windows Message Queue HDU - 1509
Message queue is the basic fundamental of windows system. For each process, the system maintains a message queue. If something happens to this process, such as mouse click, text change, the system will add a message to the queue. Meanwhile, the process will do a loop for getting message from the queue according to the priority value if it is not empty. Note that the less priority value means the higher priority. In this problem, you are asked to simulate the message queue for putting messages to and getting message from the message queue.
Input
There's only one test case in the input. Each line is a command, "GET" or "PUT", which means getting message or putting message. If the command is "PUT", there're one string means the message name and two integer means the parameter and priority followed by. There will be at most 60000 command. Note that one message can appear twice or more and if two messages have the same priority, the one comes first will be processed first.(i.e., FIFO for the same priority.) Process to the end-of-file.
Output
For each "GET" command, output the command getting from the message queue with the name and parameter in one line. If there's no message in the queue, output "EMPTY QUEUE!". There's no output for "PUT" command.
Sample Input
GET PUT msg1 10 5 PUT msg2 10 4 GET GET GET
Sample Output
EMPTY QUEUE! msg2 10 msg1 10 EMPTY QUEUE!
题意：
接收消息与发出消息
PUT为放入消息 下一行输入消息 消息包括消息的序号 信息 优先级
GET为得到消息 有消息输出消息 没消息输出空
首先比较优先级 优先级小的先输出 优先级相同时序号小的先输出
思路：
创建优先队列即可 注意题目中的优先条件
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct node
{
int x,y,num;// x 信息大小 y优先级 num 存入序号
string z;
friend bool operator < (const node a,const node b)
{
if(a.y==b.y) //优先级相同 序号小的优先
return a.num>b.num;
return a.y>b.y; //优先级小的先输出
}
} k;
priority_queue <node> q;
int main()
{
string s;
int n=1;
while(cin>>s)
{
if(s=="GET")
{
if(q.empty())
cout<<"EMPTY QUEUE!"<<endl;
else
{
node m;
m=q.top();
cout<<m.z<<" "<<m.x<<endl;
q.pop();
}
}
else
{
cin>>k.z>>k.x>>k.y;
k.num=n;
n++;
q.push(k);
}
}
while (!q.empty()) q.pop();//清空序列
return 0;
} G. POJ 3669 Meteor Shower
Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.
The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.
Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).
Determine the minimum time it takes Bessie to get to a safe place.
Input
- Line 1: A single integer: M
- Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti
Output
- Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.
Sample Input
4 0 0 2 2 1 2 1 1 2 0 3 5
Sample Output
5
思路：
先用一个数组（final_map）存储 n个陨石过后形成的最终地图。
0 表示安全位置，输入陨石时用优先队列存储，按照陨石到达的时间给陨石排序。
然后从（0,0）位置广搜，搜到 final_map 中的 0 （安全位置）时直接结束。
搜索要按照时间根据实时地图（mapp）搜索,因为有些路是实时地图可以走的，而最终地图中的路被后来的陨石破坏。
搜索过程中高及时更新实时地图，当前位置的下一秒有陨石的话就在当前时间更新地图。因为你和陨石同时到达一个位置时，是行不通的。
如果搜不到安全位置就返回-1。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
int final_map[550][550]; // 所有陨石到达后最终形成的地图
int mapp[550][550]; // 陨石坠落的实时地图
int vis[550][550];
int fx[4] = {0, 1, 0, -1};
int fy[4] = {1, 0, -1, 0};
struct ys //陨石到达的坐标时间
{
int x, y, t;
};
struct now //当前坐标与时间
{
int x, y, time;
};
struct cmp
{
bool operator()(const ys &x, const ys &y)
{
return x.t > y.t; //陨石到达时间早的排在队首
}
};
priority_queue<ys, vector<ys>, cmp> que; //创造一个按照陨石到达时间从小到大的优先级队列
void meteor(int x, int y, int ma[][550]) // 每颗陨石会对（x,y）上下左右造成陨石坑
{
ma[x][y] = 1; // 1代表 不能走的路
if (x - 1 >= 0) //地图的范围为 x,y>0
ma[x - 1][y] = 1;
if (y - 1 >= 0)
ma[x][y - 1] = 1;
ma[x][y + 1] = 1;
ma[x + 1][y] = 1;
return;
}
int bfs()
{
mem(vis);
queue<now> qq; //创建一个队列qq
now fir, next;
fir.x = 0;
fir.y = 0;
fir.time = 0;
qq.push(fir); //把起点（0,0）入队
while (!qq.empty())
{
ys to = que.top(); // to 是最先到达的陨石
now p = qq.front(); // p 是当前位置 接下来对 p 一周进行广搜
qq.pop();
if (final_map[p.x][p.y] == 0) // 如果在最终的地图上 点p 所在的位置是安全的 就表明到达安全位置
{
return p.time; // 输出 到达p点所用的时间
}
while (p.time == to.t - 1) //如果当前位置的下一秒 有陨石坠落 就修改实时地图
{
if (que.empty()) //如果 陨石队列为空 表示实时地图以及是最终的地图（final_map）就放心的走了（break）
break;
meteor(to.x, to.y, mapp); //否则 更新实时地图
que.pop();//更新完让最前面的陨石出队
to = que.top(); //to指向下一个陨石 这里用while是因为可能有多个陨石同一时间坠落
}
/*下面没什么好说的了 地图更新完后 常规对bfs做法*/
for (int i = 0; i < 4; i++)
{
next.x = p.x + fx[i];
next.y = p.y + fy[i];
if (next.x >= 0 && next.x < 500 && next.y >= 0 && next.y < 500 && mapp[next.x][next.y] == 0 && vis[next.x][next.y] == 0)
{
next.time = p.time + 1;
qq.push(next);
vis[next.x][next.y] = 1;
}
}
}
return -1;//如果不能到达安全位置 就返回-1
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
mem(mapp);
mem(final_map);
int n;
cin >> n;
int x, y, t;
ys p;
while (n--)
{
cin >> x >> y >> t;
meteor(x, y, final_map); //每次到达一颗陨石 final_map就修改一次 一直到所有的陨石都到达了 得出最终的地图(final_map)
p.x = x;
p.y = y;
p.t = t;
que.push(p); // 把陨石到达的坐标以及时间入队 队列中会按照到达的时间进行排序
}
int k = bfs();
cout << k << endl;
return 0;
}H - 骑士 HDU - 1372
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.
题意：
与象棋中马走日相同 给定起始坐标和终点坐标 求最少从起始坐标到终点坐标位置
思路：
简单bfs 详细看代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int Map[10][10];//地图
int x1,x2,y1,y2,num;
string s1,s2;
int steps[8][2]={{-2,1},{2,1},{1,2},{-1,2},{-2,-1},{2,-1},{1,-2},{-1,-2}};//八个方向
struct node
{
int x,y,time;// time 即步数
};
int bfs()
{
queue<node>q;
memset(Map,0,sizeof Map);
node now,next;//now 为此时位置 next 为下一位置
now.x=x1;
now.y=y1;
now.time=0;
Map[now.x][now.y]=1;//标记
q.push(now);//放入队列
while(!q.empty())
{
now=q.front();
q.pop();
if(now.x==x2&&now.y==y2)//若到达 返回步数
{
return now.time;
}
for(int i=0;i<8;i++)//下一步 八个方向
{
next.x=now.x+steps[i][0];
next.y=now.y+steps[i][1];
if(next.x==x2&&next.y==y2)//若下一步直接到达 返回此时步数+1
return now.time+1;
if(next.x<0||next.x>=8||next.y<0||next.y>=8||Map[next.x][next.y])//判断边界且未到达过
continue;
next.time=now.time+1;//记录步数
Map[next.x][next.y]=1;//标记状态
q.push(next);
}
}
return 0;
}
int main()
{
while(cin>>s1>>s2)
{
num=0;
x1=s1[0]-'a';
y1=s1[1]-'1';
x2=s2[0]-'a';
y2=s2[1]-'1';
int num=bfs();
cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<num<<" knight moves."<<endl;
}
return 0;
} I - 胜利大逃亡 HDU - 1253
Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.
魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.
Input
输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫)
特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.
Output
对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.
Sample Input
1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0
Sample Output
(11)请无视括号两位数打不上去
思路：
与二维数组bfs题一样，开个三维数组 套模板即可
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int x,y,z;
int num;
};
node Now,Next;
int a,b,c,T;
int Map[52][52][52];//标记状态
int step[6][3]= {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};//六个方向
int bfs()
{
queue<node>q;
Now.x=0,Now.y=0,Now.z=0,Now.num=0;
q.push(Now);
while(!q.empty())
{
Next=q.front();
q.pop();
if(Next.num>T-1)
return -1;
for(int i=0; i<6; i++)
{
Now.x=Next.x+step[i][0];
Now.y=Next.y+step[i][1];
Now.z=Next.z+step[i][2];
Now.num=Next.num+1;
if(Now.x==a-1&&Now.y==b-1&&Now.z==c-1)//到达则返回
return Now.num;
if(Now.x>=0&&Now.x<a&&Now.y>=0&&Now.y<b&&Now.z>=0&&Now.z<c&&
Map[Now.x][Now.y][Now.z]!=1)//判断边界且不为墙
{
Map[Now.x][Now.y][Now.z]=1;
q.push(Now);
}
}
}
return -1;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d%d",&a,&b,&c,&T);
for(int i=0; i<a; i++)
for(int j=0; j<b; j++)
for(int k=0; k<c; k++)
{
scanf("%d",&Map[i][j][k]);//输入三维数组
}
if(a==1&&b==1&&c==1)
{
printf("0\n");
continue;
}
if(Map[a-1][b-1][c-1]||a+b+c-3>T)//若 终点为墙或者时间不够
{
printf("-1\n");
continue;
}
printf("%d\n",bfs());
}
return 0;
}J. HDU 1495 非常可乐(不会)
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3 4 1 3 0 0 0
Sample Output
NO 3
题意：三个杯子中的可乐互相倒，最终有两个杯子可乐量相同，并且另外一个杯子为空表明操作成功。
思路：这道题说了要找最少步数，就应该想到用BFS。
三个杯子互相倒就会有 3！ = 6 种操作：
k1->k2 k1->k3 k2->k1 k2->k3 k3->k1 k3->k2
然后模拟互相倒水时，杯子中可乐的变化就行了
具体解释看代码中的注释，写出来一种操作，其他5种类似。
AC代码：
/*HDU 1495*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
int s,n,m;
int vis[105][105][105];//标记这种操作是否用过
struct node
{
int k1;// s杯中的量
int k2;// n杯中的量
int k3;// m杯中的量
int step;
};
int bfs()
{
mem(vis);
queue<node> que;
node fir,p,next;
fir.k1=s; //刚开始 S为满的 n和m都是空的
fir.k2=0;
fir.k3=0;
fir.step=0;
que.push(fir);
while(!que.empty())
{
p=que.front();
que.pop();
if((p.k1==p.k2 && p.k3==0) || (p.k1==p.k3 && p.k2==0) || (p.k2==p.k3 && p.k1==0)) //当有两个杯子的可乐相同并且另外一个杯子为空时完成任务
{
return p.step;//返回所花的步数
}
for(int i=1;i<=6;i++) // 共有6种操作：1->2, 1->3, 2->1, 2->3, 3->1, 3->2
{
if(i==1) // k1->k2
{
if(p.k1+p.k2<=n) //k1 往 k2里到 k1+k2还小于 n 表示倒不满
{
next.k1=0; // n 倒不满 说明 s已经为空
next.k2=p.k1+p.k2; // k2 的量为k1所有的加上k2原来有的
next.k3=p.k3; // k3没有操作 还是原来的量
}
else // n 倒满了 s中还有剩余 (k1>=0)
{
next.k2=n; // n 倒满了 所以k2就是最大量 n
next.k1=p.k1+p.k2-n; // s->n的量为（n-k2) 所以 s中剩余的量为 k1-(n-k2)
next.k3=p.k3;
}
}
if(i==2) // k1->k3
{
if(p.k1+p.k3<=m)
{
next.k1=0;
next.k3=p.k1+p.k3;
next.k2=p.k2;
}
else
{
next.k3=m;
next.k1=p.k1+p.k3-m;
next.k2=p.k2;
}
}
if(i==3) // k2->k1
{
if(p.k1+p.k2<=s)
{
next.k2=0;
next.k1=p.k1+p.k2;
next.k3=p.k3;
}
else
{
next.k1=s;
next.k2=p.k1+p.k2-s;
next.k3=p.k3;
}
}
if(i==4) // k2->k3
{
if(p.k2+p.k3<=m)
{
next.k2=0;
next.k3=p.k2+p.k3;
next.k1=p.k1;
}
else
{
next.k3=m;
next.k2=p.k2+p.k3-m;
next.k1=p.k1;
}
}
if(i==5) // k3->k1
{
if(p.k1+p.k3<=s)
{
next.k3=0;
next.k1=p.k1+p.k3;
next.k2=p.k2;
}
else
{
next.k1=s;
next.k3=p.k1+p.k3-s;
next.k2=p.k2;
}
}
if(i==6) // k3->k2
{
if(p.k3+p.k2<=n)
{
next.k3=0;
next.k2=p.k3+p.k2;
next.k1=p.k1;
}
else
{
next.k2=n;
next.k3=p.k3+p.k2-n;
next.k1=p.k1;
}
}
if(vis[next.k1][next.k2][next.k3]==0) // 如果这种操作没有操作过的话
{
vis[next.k1][next.k2][next.k3]=1; //标记已操作
next.step=p.step+1;// 步数+1
que.push(next);
}
}
}
return -1;//队空后还没有找到 合适的ans就返回-1
}
int main()
{
while(cin>>s>>n>>m && s)
{
if(s&1) //如果S为奇数 直接输出NO
{
cout<<"NO"<<endl;
continue;
}
int ans = bfs();
if(ans!=-1) // 如果ans不等于-1 说明操作成功
cout<<ans<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}数论写法：
/*HDU 1495*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 1<<30
#define N 210
using namespace std;
int gcd(int a,int b)
{
if(a%b==0)
return b;
return gcd(b,a%b);
}
int main()
{
int s,n,m;
while(1)
{
scanf("%d%d%d",&s,&n,&m);
if(s==0&&n==0&&m==0)
break;
if(s%2)
{
printf("NO\n");
continue;
}
s=s/gcd(s,gcd(n,m));
if(s%2)
printf("NO\n");
else
printf("%d\n",s-1);
}
return 0;
}
京公网安备 11010502036488号