HPU 暑期集训 Day 10
今天没讲题，加练，没啥好说的，除了脑仁疼就是脑仁疼。还有两道似乎是用到DFS的是真的写不出来了。慢慢补吧。
Knight Moves
Description:
Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.
Input
The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.
Output
For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.
Sample Input
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Sample Output
5
28
0
Problem solving:
简单的BFS模板题，8个方向查找即可。
Code:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node{
int x,y;
};
const int maxn=305;
int vis[maxn][maxn];
int step[maxn][maxn];
int n,m,sx,sy,ex,ey;
int d[8][2]={2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};
void bfs()
{
queue<node> q;
node now,mid;
vis[sx][sy]=1;
now.x=sx,now.y=sy;
q.push(now);
while(!q.empty())
{
mid=q.front();
q.pop();
for(int i = 0 ;i<8;i++)
{
now.x=mid.x+d[i][0];
now.y=mid.y+d[i][1];
if(now.x<0||now.x>=m||now.y<0||now.y>=m||vis[now.x][now.y]) continue;
vis[now.x][now.y]=1;
step[now.x][now.y]=step[mid.x][mid.y]+1;
q.push(now);
}
}
}
int main()
{
cin>>n;
while(n--)
{
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
cin>>m>>sx>>sy>>ex>>ey;
bfs();
cout<<step[ex][ey]<<endl;
}
}变形课
Description:
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
Sample Output
Yes.
Harry 可以念这个咒语:"big-got-them".
Problem solving:
这道题我的想法是用邻接表存图，把输入的每一个单词的首字母与最后一个字母当成两个节点，并且是有向边，然后bfs以'b'为起点查找如果能找到'm'与它相连，就输出Yes，反之输出'No'.
这道题还有一个很难受的地方就是输入、、、多组套多组，里面的多组还有结束条件。不过写完这道题也算是学会了，这样写就行。
while(cin>>s)
{
while(s!='0')
{
cin>>s;
}
}Code:
#include<bits/stdc++.h>
using namespace std;
int ma[100][100],vis[100];
bool bfs(int x)
{
queue<int> q;
q.push(x);
vis[x]=1;
while(!q.empty())
{
x=q.front();
if(x=='m'-'0') return 1;
q.pop();
for(int i='a'-'0';i<='z'-'0';i++)
{
if(ma[x][i]==1&&!vis[i])
{
vis[i]=1;
// cout<<x<<" "<<i<<endl;
// cout<<ma[x][i]<<"?"<<ma[i][x]<<endl;
q.push(i);
}
}
}
return 0;
}
int main()
{
string s;
while(cin>>s)
{
memset(ma,0,sizeof(ma));
memset(vis,0,sizeof(vis));
while(s!="0")
{
char sx=s[0],ex=s[s.size()-1];
// cout<<sx-'0'<<" "<<ex-'0'<<endl;
ma[sx-'0'][ex-'0']=1;
cin>>s;
}
if(bfs('b'-'0')) puts("Yes.");
else puts("No.");
}
}Pet
Description:
一天早上小明醒来时发现他的宠物仓鼠不见了。 他在房间寻找但是没找到仓鼠。 他想用奶酪诱饵去找回仓鼠。 他把奶酪诱饵放在房间并且等待了好几天。 但是可怜的小明除了老鼠和蟑螂没见到任何东西。 他找到学校的地图发现地图上没有环路，并且学校里的每个站点都可以从他的房间到达。 奶酪诱饵的手册提到在距离D之内宠物必定会被吸引回来. 你的任务是帮助小明从给定的地图中有多少可能的站点是仓鼠的藏身处. 假定仓鼠一直藏在学校的某个站点并且两个相邻站点间的距离都是1个单位。
Input
输入包含多组数据。 第一行一个整数T (0<T<=10), 表示测试数据的组数。 每组数据, 第一行包含两个整数 N (0<N<=100000) 和 D(0<D<N). N 是学校里的站点数， D 是诱饵的影响距离。 下面 N-1行为地图描述, 每行一对 x 和 y(0<=x,y<N), 用一个空格隔开, 表示x和y两个站点是相邻的。小明的房间用0表示。
Output
对于每组数据，输出可能找到仓鼠的站点数。
Sample Input
1
10 2
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
6 9
Sample Output
2
Problem solving:
题意还挺好理解的，就是问你一个图距离顶点距离大于某一值得点有多少个。构建一个图，因为现在已经知道了0是顶点，直接从0开始bfs查找，找出每个点距离0的最远距离，与给的定值进行比较即可。
注意多组输入每次需要初始化（我因为这个WA了一发。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1e5+10;
vector<int> v[maxn];
int dis[maxn],vis[maxn],ans;
using namespace std;
int n,d,t,x,y;
void bfs(int x)
{
queue<int> q;
q.push(x);
vis[x]=1;dis[x]=0;
while(!q.empty())
{
x=q.front();
q.pop();
for(int i=0;i<v[x].size();i++)
{
if(v[x][i]&&!vis[v[x][i]])
{
q.push(v[x][i]);
vis[v[x][i]]=1;
dis[v[x][i]]=dis[x]+1;
}
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
ans=0;
scanf("%d %d",&n,&d);
for(int i=0;i<n;i++)
v[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
bfs(0);
for(int i=0;i<n;i++)
{
if(dis[i]>d) ans++;
}
printf("%d\n",ans);
}
}蜘蛛牌
Description:
蜘蛛牌是windows xp操作系统自带的一款纸牌游戏，游戏规则是这样的：只能将牌拖到比她大一的牌上面（A最小，K最大），如果拖动的牌上有按顺序排好的牌时，那么这些牌也跟着一起移动，游戏的目的是将所有的牌按同一花色从小到大排好，为了简单起见，我们的游戏只有同一花色的10张牌，从A到10，且随机的在一行上展开，编号从1到10，把第i号上的牌移到第j号牌上，移动距离为abs(i-j)，现在你要做的是求出完成游戏的最小移动距离。
Input
第一个输入数据是T，表示数据的组数。
每组数据有一行，10个输入数据，数据的范围是[1,10]，分别表示A到10，我们保证每组数据都是合法的。
Output
对应每组数据输出最小移动距离。
Sample Input
1
1 2 3 4 5 6 7 8 9 10
Sample Output
9
Problem solving:
暂无（毫无思路题，据说是dfs）
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
逃离迷宫
Description:
给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？
Input
第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数，(x 1, y 1), (x 2, y 2)表示两个位置，其中x 1，x 2对应列，y 1, y 2对应行。
Output
每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。
Sample Input
2
5 5
...**
.*.
.....
.....
....
1 1 1 1 3
5 5
...*
.*.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes
Problem solving:
这也是一道查找的题，给了你起点和终点和最大拐弯次数，问你能不能从起点走到终点。我选择了bfs，其实是一道挺简单的题，难点就是如何得到当前转弯的次数。我一开始想着用x，y坐标的差值来表示，但是又麻烦又不好理解。然后我在网上看到了一种写法。就是在bfs的过程中，每选择了一个方向就按照这个方向一直走下去直到越界或者到了走不了的点。这一步描述的如果你不是很懂，可以参考一下下面代码我加上的注释。
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,ex,ey,k;
char s[105][105];
int vis[105][105];
struct node{
int x,y,flag;//flag就是用来存当前的拐弯次数
};
int d[4][2]={1,0,0,1,0,-1,-1,0};
bool bfs()
{
queue<node> q;
node now,mid;
now.x=sx,now.y=sy,now.flag=-1;//初始的转弯次数设为-1是因为第一次走是不算入转弯次数的
vis[sx][sy]=1;
q.push(now);
while(!q.empty())
{
// cout<<"?";
now=q.front();
q.pop();
if(now.flag>=k) continue;//如果此时转弯次数已经大于k了，就没有走下去的必要了。这一点在这种写法中很重要
for(int i=0;i<4;i++)
{
mid.x=now.x+d[i][0];
mid.y=now.y+d[i][1];
mid.flag=now.flag+1;//此时你选择了一个方向
while(1)//沿着这个方向一直走下去
{
if(mid.x<0||mid.x>=n||mid.y<0||mid.y>=m||s[mid.x][mid.y]=='*') break;//如果越界了或者不能走了，就说明沿着这个方向一直走走不下去了，break就行
if(mid.x==ex&&mid.y==ey) return 1;//如果当前走到的点与终点相等，就说明可以走到，返回true
if(vis[mid.x][mid.y]==0)
{
vis[mid.x][mid.y]=1;
q.push(mid);
}
mid.x+=d[i][0];//沿着这个方向更新到下一个走到的点的x，y坐标
mid.y+=d[i][1];
}
}
}
return 0;
}
int main()
{
cin>>t;
while(t--)
{
memset(vis,0,sizeof(vis));
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>s[i];
cin>>k>>sy>>sx>>ey>>ex;//这有个坑，它先输入的是y的值
sx--,sy--,ex--,ey--;
if(bfs()) puts("yes");
else puts("no");
}
}Kaitou Kid - The Phantom Thief (2)
Description:
破解字迷之后，你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石，并离开展馆。整个展馆呈矩形分布，划分为N*M个区域，有唯一的入口和出口（不能从出口进入，同样不能从入口出去）。由某个区域可直接移动至相邻四个区域中的一个，且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石，无需耗时。问至少要封锁几个区域（可以封锁放有宝石的区域，但不能封锁入口和出口）才能保证Kid无法完成任务。
Input
输入的第一行有一个整数C，代表有C组测试数据。每组测试数据的第一行有三个整数N，M，T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图，其中包括：
'S'：入口
'E'：出口
'J'：放有宝石的区域，至少出现一次
'.'：空白区域
'#'：墙
Output
对每组测试数据，输出至少要封锁的区域数。
Sample Input
2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...
EJ...
Sample Output
0
2
Problem solving:
暂无（据说是bfs+dfs）
Code:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //
A计划
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
Problem solving:
哇，这道题坑的一批。最后玄学过题
就是个三维的bfs，而且给定了只有两层。
因为遇到传送门进行传送的时候是不需要耗费时间的，所以传送门那需要特殊处理一下（可以想一下，如果传送门传送过去的位置还是传送门，就成死循环了。如果传送门传送过去是墙，也可以直接看做这个传送门是一堵墙）
Code:
#include<bits/stdc++.h>
using namespace std;
int c,n,m,t;
struct node{
int x,y,z,step;
};
int d[4][2]={1,0,0,1,0,-1,-1,0},vis[2][15][15],flag;
char s[2][15][15];
node now,mid,meizi;
void bfs()
{
queue<node> q;
q.push(now);
vis[now.x][now.y][now.z]=1;
while(!q.empty())
{
mid=q.front();
q.pop();
if(s[mid.x][mid.y][mid.z]=='P'&&mid.step<=t)
{
flag=1;
return ;
}
for(int i=0;i<4;i++)
{
meizi=mid;
meizi.y+=d[i][0];
meizi.z+=d[i][1];
meizi.step+=1;
if(meizi.step>t||meizi.y<0||meizi.y>=n||meizi.z<0||meizi.z>=m||vis[meizi.x][meizi.y][meizi.z]||s[meizi.x][meizi.y][meizi.z]=='*')
continue;
vis[meizi.x][meizi.y][meizi.z]=1;
if(s[meizi.x][meizi.y][meizi.z]=='#'&&s[(meizi.x+1)%2][meizi.y][meizi.z]!='*'&&!vis[(meizi.x+1)%2][meizi.y][meizi.z])
meizi.x=(meizi.x+1)%2;
q.push(meizi);
}
}
}
int main()
{
cin>>c;
while(c--)
{
memset(vis,0,sizeof(vis));
cin>>n>>m>>t;
for(int i=0;i<2;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<m;k++)
{
cin>>s[i][j][k];
if(s[i][j][k]=='S')
{
now.x=i,now.y=j,now.z=k,now.step=0;
}
}
}
}
for(int j=0;j<n;j++)
{
for(int k=0;k<m;k++)
{
if(s[0][j][k]=='#'&&s[1][j][k]=='*')
{
s[0][j][k]=s[1][j][k]='*';
}
if(s[0][j][k]=='*'&&s[1][j][k]=='#')
{
s[0][j][k]=s[1][j][k]='*';
}
if(s[0][j][k]=='#'&&s[1][j][k]=='#')
{
s[0][j][k]=s[1][j][k]='*';
}
}
}
flag=0;
bfs();
if(flag) puts("YES");
else puts("NO");
}
}Nightmare
Description:
Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.
Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.
Here are some rules:
- We can assume the labyrinth is a 2 array.
- Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
- If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
- If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
- A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
- The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.
InputThe input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius' start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius' target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.
Output
For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.
Sample Input
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1
Sample Output
4
-1
13
Problem solving:
这道题我是用bfs来做的，跟一种题很像，就是给你规定一个时间看能否走出迷宫之类的问题。
但是这道题有一种新的规则，就是如果走到某些特殊的点。时间会更新一次。
0是墙，不可以走
1是路
2是起点
3是终点
4是可以重置时间的点
刚开始看到这里的时候我想着肯定要经过很负责的处理。但是后来发现其实我们只需要知道这两点就可以了。并且题目中规定如果时间为0就不能继续走下去了。
- 每个点都是可以重复访问的
- 可以刷新时间的点我们只走一次
第一点到不需要怎么理解，就是第二点我们该如何理解呢？
如果同一个位置的炸弹你第二次走到了它上面就说明此时已经不是最优解了。所以每个刷新时间的点我们每次走完之后就把它存为0——即墙。
关于第二点的理解还有另一种解释方式:
上同一位置是bomb离explode的时间长短来标记。简言之，如果第二次踏上一个位置，那么找出路已用的时间肯定是增加了，那为啥还要走上这条路呢？唯一的追求就是bomb离爆炸的时间增大了。所以可以利用这个条件来标记了。每次在入队前检查下爆炸时间是否比上次在同一位置的大，若是，则入队；反之，入队无意义了。从以上的分析中可以引出另一思路，也就是只要进入位置4，那么bomb就会延时到6分钟，最大的延时时间。换句话说，下次再进入该4位置，也不会获得更大的延时时间了。所以，只要访问过位置4了，就可以直接标记为0位置，表明下次不可在访问。详见代码二。
转载于：clouddyx
其实想一下也确实是，假设我们现在走到了一个可以重置时间的点，如果下次在走到这，是不是就一直循环下去了，所以按照这个理解也可以。
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10][10];
struct node{
int x,y,step,time;
};
int d[4][2]={1,0,0,1,0,-1,-1,0};
int ans;
node now,mid;
void bfs()
{
queue<node> q;
q.push(now);
while(!q.empty())
{
// cout<<"?"<<endl;
now=q.front();
q.pop();
if(now.time<=0) continue;
if(a[now.x][now.y]==3)
{
ans=now.step;
return ;
}
for(int i=0;i<4;i++)
{
mid.x=now.x+d[i][0];
mid.y=now.y+d[i][1];
mid.step=now.step+1;
mid.time=now.time-1;
if(mid.x<0||mid.x>=n||mid.y<0||mid.y>=m||mid.time<=0||a[mid.x][mid.y]==0) continue;
if(a[mid.x][mid.y]==4)
{
a[mid.x][mid.y]=0;
mid.time=6;
}
q.push(mid);
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
ans=-1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]==2)
{
now.x=i,now.y=j,now.step=0,now.time=6;
}
}
}
bfs();
cout<<ans<<endl;
}
}胜利大逃亡
Description:
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
Problem solving:
简单的三维bfs，直接写就行了，六个方向。注意多组输入需要初始化，我又是这WA了一次。。。
Code:
#include<bits/stdc++.h>
using namespace std;
int a,b,c,k;
int s[51][51][51];
int vis[51][51][51];
struct node{
int x,y,z,step;
};
node mz,mid,ne;
int d[6][3]={1,0,0, -1,0,0, 0,1,0, 0,-1,0, 0,0,1,0,0,-1},ans;
void bfs()
{
mz.x=mz.y=mz.z=mz.step=0;
queue<node> q;
q.push(mz);
vis[0][0][0]=1;
while(!q.empty())
{
mid=q.front();
q.pop();
if(mid.step>k)
{
return ;
}
if(mid.x==a-1&&mid.y==b-1&&mid.z==c-1&&mid.step<=k)
{
ans=mid.step;
return ;
}
for(int i=0;i<6;i++)
{
ne.x=mid.x+d[i][0];
ne.y=mid.y+d[i][1];
ne.z=mid.z+d[i][2];
if(ne.x<0||ne.x>=a||ne.y<0||ne.y>=b||ne.z<0||ne.z>=c||vis[ne.x][ne.y][ne.z]||s[ne.x][ne.y][ne.z]==1)
continue;
ne.step=mid.step+1;
vis[ne.x][ne.y][ne.z]=1;
q.push(ne);
}
}
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
ans=-1;
scanf("%d %d %d %d",&a,&b,&c,&k);
for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
for(int k=0;k<c;k++)
{
scanf("%1d",&s[i][j][k]);
}
}
}
bfs();
printf("%d\n",ans);
}
}A strange lift
Description:
计院有一个bug电梯，可能是hyk造的，很多bug，电梯只有两个按钮，“上”和“下”，电梯每层都可以停，每层都有一个数字Ki（0<=Ki<=n），当你在一层楼，你按“上”键会到1+K1层，你按“下”键会到1-K1层。当然，电梯不能升到N以上，也不能降到1以下。例如，有一个五层楼的建筑，k1=3，k2=3，k3=1，k4=2，k5=5。从第一层开始，你可以按“上”按钮，然后你就上到第四层，如果在第一层按“下”按钮，电梯就不能做到，因为你知道它不能下到负二层。负二楼不存在。
那么，你想从A层到B层，你至少要按多少次“上”或“下”按钮呢？
Input
输入由几个测试用例组成，每个测试用例包含两行。
第一行包含三个整数n，a，b（1<=n，a，b<=200），如上文所述，第二行包含n个整数k1，k2，….kn。
单个0表示输入的结束。
Output
对于每种情况下的输入输出一个整数，当你在A层，你必须按下按钮的最少次数，你想去B层。如果你不能到达B层，打印“-1”。
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3
Problem solving:
也是一道存图的题。每次存的时候注意判断第二个点与0跟n的大小关系。也是有向图。
注意初始化！！！又是这样WA了一次。
Code:
#include<bits/stdc++.h>
using namespace std;
int n,a,b,meizi;
int s[250][250],ans;
int vis[250],step[250];
void bfs(int x)
{
queue<int> q;
q.push(x);
vis[x]=1,step[x]=0;
while(!q.empty())
{
int mid=q.front();
q.pop();
// cout<<mid<<endl;
if(mid==b)
{
// cout<<"?"<<endl;
ans=step[mid];
return ;
}
for(int i=1;i<=n;i++)
{
// cout<<x<<" "<<i<<" "<<s[x][i]<<endl;
if(s[mid][i]&&vis[i]==0)
{
q.push(i);
vis[i]=1;
step[i]=step[mid]+1;
}
}
}
}
int main()
{
while(cin>>n&&n)
{
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
memset(s,0,sizeof(s));
ans=-1;
cin>>a>>b;
for(int i=1;i<=n;i++)
{
cin>>meizi;
if(i+meizi>=1&&i+meizi<=n) s[i][meizi+i]=1;
if(i-meizi>=1&&i-meizi<=n) s[i][i-meizi]=1;
}
bfs(a);
cout<<ans<<endl;
}
}
投递小米集团等公司6个岗位 >