Day9

Day9

今天是 dfs 和 bfs 加训
继续学习 dfs 和 bfs,毕竟这一块还是非常重要的

OJ链接:https://vjudge.net/contest/314510#overview

Knight Moves

Problem 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sample Input
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Sample Output
5
28
0

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
int c, d;
int ans, n;
int vis[400][400];
int dd[8][2] = {
-2, 1,
-1, 2,
1, 2,
2, 1,
-2, -1,
-1, -2,
1, -2,
2, -1
};
struct node{
int x, y, step;
};
void bfs(int x, int y)
{
ans = 0;
memset(vis, 0, sizeof vis);
queue<node> q;
node e1, e2;
e1.x = x, e1.y = y, e1.step = 0;
q.push(e1);
vis[e1.x][e1.y] = 1;
while(!q.empty())
{
e1 = q.front();
q.pop();
if(e1.x == c && e1.y == d)
{
ans = e1.step;
break;
}
for(int i = 0; i < 8; i ++)
{
e2.x = e1.x + dd[i][0];
e2.y = e1.y + dd[i][1];
if(e2.x >= 0 && e2.y >= 0 && e2.x < n && e2.y < n && vis[e2.x][e2.y] == 0)
{
vis[e2.x][e2.y] = 1;
e2.step = e1.step + 1;
q.push(e2);
}
}
}
cout << ans << endl;
}
int main()
{
int T;
int a, b;
cin >> T;
while(T --)
{
cin >> n;
cin >> a >> b >> c >> d;
bfs(a, b);
}

return 0;
}

变形课

Problem Description
呃……变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行,每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出”Yes.”,否则就输出”No.”(不要忽略了句号)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
Sample Output
Yes.

Hint
Harry 可以念这个咒语:"big-got-them".

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
string ss;
bool vis[1000 + 10];

int i;
int flag;
struct node{
int x, y;
}a[1000 + 10];



void dfs(int x)
{
if(a[x].y == 'm')
{
flag = 1;
return;
}
for(int j = 0; j < i; j ++)
{
if(a[x].y == a[j].x && vis[j] == 0)
{
vis[j] = 1;
dfs(j);
}
}
}
int main()
{
while(cin >> ss)
{
memset(vis, 0, sizeof vis);
flag = 0;
i = 0;
while(cin >> ss)
{
if(ss[0] != '0')
{
a[i].x = ss[0];
a[i].y = ss[ss.size() - 1];
i ++;
}
else break;
for(int j = 0; j < i; j ++)
{
if(a[j].x == 'b')
{
vis[j] = 1;
dfs(j);
}
}
}
if(flag) puts("Yes.");
else puts("No.");
}

return 0;
}

Pet

Problem 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
对于每组数据,输出可能找到仓鼠的站点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
bfs解法:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
vector<int> v[maxx];
int n, d;
bool vis[maxx];
int dis[maxx];
void bfs()
{
memset(vis, 0, sizeof vis);
memset(dis, 0, sizeof dis);
queue<int> q;
q.push(0);
vis[0] = 1;
dis[0] = 0;
int cnt = 0;
while(!q.empty())
{
int f = q.front();
q.pop();
if(dis[f] > d)
{
cnt ++;
}
for(int i = 0; i < v[f].size(); i ++)
{
if(vis[v[f][i]] == 0)
{
dis[v[f][i]] = dis[f] + 1;
vis[v[f][i]] = 1;
q.push(v[f][i]);
}
}
}
printf("%d\n",cnt);
}


int main()
{
// ios::sync_with_stdio(false);
int T;
int a, b;
while(~scanf("%d",&T))
{
while(T --)
{
scanf("%d %d",&n, &d);
for(int i = 0; i < n; i ++) v[i].clear();
for(int i = 0;i < n - 1; i ++)
{
scanf("%d %d",&a, &b);
v[a].push_back(b);
}
bfs();
}
}
return 0;
}



dfs解法:
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 50 ;

vector<int>G[maxn] ;
int ans ;
int n ,m ;
int vis[maxn] ;

void dfs(int st ,int l)
{
if ( l > m ) ans ++ ;
int len = G[st].size() ;
for (int i = 0 ; i < len ; i ++ )
{
if ( !vis[G[st][i]] )
{
dfs(G[st][i] ,l + 1 ) ;
vis[G[st][i]] = 1;
}
}
}

int main() {
int t ;
while(scanf("%d",&t)!=EOF)
{
while ( t -- )
{
ans = 0 ;
int a ,b ;
scanf("%d %d",&n ,&m);
for (int i = 0 ; i <= n ; i ++ ) G[i].clear() ,vis[i] = 0 ;
for (int i = 1 ; i <= n - 1 ; i ++ )
{
scanf("%d %d",&a ,&b ) ;
G[a].push_back(b) ;
//G[b].push_back(a) ;
}
dfs(0 ,0 ) ;
printf("%d\n",ans) ;
}
}

return 0;
}

蜘蛛牌

Problem Description
蜘蛛牌是windows xp操作系统自带的一款纸牌游戏,游戏规则是这样的:只能将牌拖到比她大一的牌上面(A最小,K最大),如果拖动的牌上有按顺序排好的牌时,那么这些牌也跟着一起移动,游戏的目的是将所有的牌按同一花色从小到大排好,为了简单起见,我们的游戏只有同一花色的10张牌,从A到10,且随机的在一行上展开,编号从1到10,把第i号上的牌移到第j号牌上,移动距离为abs(i-j),现在你要做的是求出完成游戏的最小移动距离。
Input
第一个输入数据是T,表示数据的组数。
每组数据有一行,10个输入数据,数据的范围是[1,10],分别表示A到10,我们保证每组数据都是合法的。
Output
对应每组数据输出最小移动距离。

1
2
3
4
5
Sample Input
1
1 2 3 4 5 6 7 8 9 10
Sample Output
9

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
思路:桶排原理记录每张牌的位置,遍历每张牌,枚举所有可能位置。
将牌的大小作为下标。然后依次遍历。。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int MAX = 0x3f3f3f3f;
char a[100];
char visit[100];
int ans;

void dfs(int num, int sum)
{
if (num==9)
{
if(sum<ans)
{
ans = sum;
}
return ;
}
for(int i=1; i<10; i++)
{
if(visit[i]==0)
{
visit[i] = 1;
for(int j=i+1; j<=10; j++)
{
if(visit[j]==0)
{
dfs(num+1, sum + abs(a[j]-a[i]));
break;
}
}
visit[i] = 0;
}
}
}
int main()
{
int T, x;
scanf("%d", &T);
while(T--)
{
for(int i=1; i<=10; i++)
{
scanf("%d", &x);
a[x] = i;
}
memset(visit, 0, sizeof(visit));
ans = MAX;
dfs(0, 0);
printf("%d\n", ans);
}
return 0;
}

逃离迷宫

Problem 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”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Sample Input
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;
const int mod = 1e9;
const int maxx = 1e2 + 10;
int n, m, a1, b1, a2, b2, k;
char a[maxx][maxx];
bool vis[maxx][maxx];
int flag;

int d[4][2] = {
1, 0,
-1, 0,
0, 1,
0, -1
};

struct node{
int x, y, step;
};
void bfs()
{
memset(vis, 0, sizeof vis);
queue<node> q;
node e1, e2, e3;
e1.x = a1 - 1, e1.y = b1 - 1, e1.step = -1;
q.push(e1);
vis[e1.x][e1.y] = 1;
while(!q.empty())
{
e1 = q.front();
q.pop();
if(e1.x == a2 - 1 && e1.y == b2 - 1 && e1.step <= k)
{
flag = 1;
return;
}
for(int i = 0; i < 4; i ++)
{
e2.x = e1.x + d[i][0];
e2.y = e1.y + d[i][1];
while(e2.x >= 0 && e2.y >= 0 && e2.x < n && e2.y < m && a[e2.x][e2.y] == '.')
{
if(vis[e2.x][e2.y] == 0)
{
e2.step = e1.step + 1;
vis[e2.x][e2.y] = 1;
q.push(e2);
}
e3.x = e2.x + d[i][0];
e3.y = e2.y + d[i][1];
e2 = e3;
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
scanf("%d %d",&n, &m);

for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
{
cin >> a[i][j];
}

scanf("%d %d %d %d %d",&k, &b1, &a1, &b2, &a2);
flag = 0;
bfs();
if(flag) puts("yes");
else puts("no");
}
return 0;
}

Kaitou Kid - The Phantom Thief (2)

Problem 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
对每组测试数据,输出至少要封锁的区域数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Sample Input
2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...
EJ...
Sample Output
0
2

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

char mapp[10][10];
int visit[10][10];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,o;
int sx,sy,ex,ey;
int flag;

struct stu
{
int x,y;
int d;
int flag;
};
int bfs()
{
memset(visit,0,sizeof(visit));
stu x,y;
queue<stu>root;
x.x=sx;x.y=sy;x.flag=1;x.d=0;
visit[x.x][x.y]=1;
root.push(x);
while(root.size())
{
x=root.front();
root.pop();
if(x.x==ex&&x.y==ey&&x.flag==2&&x.d<=o) return 0;
for(int i=0;i<4;i++)
{
y.x=x.x+dir[i][0];
y.y=x.y+dir[i][1];
y.d=x.d+1;
if(mapp[y.x][y.y]=='J') y.flag=2;
else y.flag=x.flag;
if(y.x<0||y.x>=n||y.y<0||y.y>=m||visit[y.x][y.y]==y.flag||mapp[y.x][y.y]=='#'||y.d>o) continue;
visit[y.x][y.y]=y.flag;
root.push(y);
}
}
return 1;
}
void dfs(int x)
{
if(bfs()) flag=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
char ma=mapp[i][j];
if(ma=='.'||ma=='J')
{
mapp[i][j]='#';
if(x>0) dfs(x-1);
if(flag) return;
mapp[i][j]=ma;
}
}
}
}
int main()
{
cin.sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
cin>>n>>m>>o;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mapp[i][j];
if(mapp[i][j]=='S') sx=i,sy=j;
if(mapp[i][j]=='E') ex=i,ey=j;
}
}
flag=0;
re=1<<30;
for(int i=0;i<=4;i++)
{
dfs(i);
if(flag)
{
cout<<i<<endl;
break;
}
}
}
return 0;
}

A计划

Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N
M(1 <= N,M <=10)。T如上所意。接下去的前NM表示迷宫的第一层的布置情况,后NM表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”,否则输出“NO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#.

..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>

using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
int n, m, p;
int ans;
char a[2][30][30];
bool vis[2][30][30];
//int step[2][30][30];
struct node{
int x, y, z;
int t;
friend bool operator < (node a, node b)
{
return a.t > b.t;
}
}e;
int d[4][2] = {
0, 1,
0, -1,
1, 0,
-1, 0
};

int bfs()
{
memset(vis, 0, sizeof vis);
queue<node> q;
node e1, e2;
e1.x = 0, e1.y = 0, e1.z = 0, e1.t = 0;
q.push(e1);
vis[e1.x][e1.y][e1.z] = 1;
while(!q.empty())
{
e1 = q.front();
q.pop();
if(e1.z == e.z && e1.x == e.x && e1.y == e.y)
{
return e1.t;
}
for(int i = 0; i < 4; i ++)
{
e2.x = e1.x + d[i][0];
e2.y = e1.y + d[i][1];
e2.z = e1.z;
if(e2.x >= 0 && e2.y >= 0 && e2.x < n && e2.y < m && vis[e2.z][e2.x][e2.y] == 0 && a[e2.z][e2.x][e2.y] != '*')
{
if(a[e2.z][e2.x][e2.y] == '#')
{
e2.z = 1 - e2.z;
if(a[e2.z][e2.x][e2.y] == '*' || a[e2.z][e2.x][e2.y] == '#') continue;
}
e2.t = e1.t + 1;
if(e2.t > p) continue;//必须剪枝
q.push(e2);
vis[e2.z][e2.x][e2.y] = 1;
}
}
}
return -1;
}

int main()
{
int T;
cin >> T;
while(T --)
{
cin >> n >> m >> p;
for(int i = 0; i < 2; i ++)
{
for(int j = 0; j < n; j ++)
{

for(int k = 0; k < m; k ++)
{
cin >> a[i][j][k];
if(a[i][j][k] == 'P')
{
e.z = i;
e.x = j;
e.y = k;
}
}
}
}
ans = bfs();
// cout << ans << endl;
if(ans != -1 && ans <= p) puts("YES");
else puts("NO");
}
return 0;
}

Nightmare

Problem 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:

  1. We can assume the labyrinth is a 2 array.
  2. 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.
  3. If Ignatius get to the exit when the exploding time turns to 0, he can’t get out of the labyrinth.
  4. 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.
  5. 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.
  6. 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.
    Input
    The 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.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
}
}

胜利大逃亡

Problem 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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

Problem 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”。

1
2
3
4
5
6
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}
}

---------------- The End ----------------
0%