KATHTHI SPOJ - KATHTHI (BFS+deque)

题目

Kathiresan is initially locked at cell (0,0) in a highly guarded rectangular prison of order RxC. He must reach the gate at (R-1,C-1) in order to escape from the prison. Kathiresan can move from any cell, to any of it’s 4 adjacent cells (North, East, West and South). If Kathiresan is currently at (x1,y1), then he can move to (x2,y2) if and only if abs(x2-x1)+abs(y2-y1) == 1 and 0<=x2<R and 0<=y2<C

Kathiresan somehow manages to get the map of the prison.
If map[x1][y1] == map[x2][y2] then Kathiresan can move from (x1,y1) to (x2,y2) without killing any guards.
If map[x1][y1] != map[x2][y2], then Kathiresan can move from (x1,y1) to (x2,y2) by killing a guard.

Given the map of the prison, find the minimum number of guards Kathiresan must kill in order to escape from the prison.
Input:

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers R and C representing the order of the rectangular prison followed by R strings representing the map of the rectangular prison.

Output:

For each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.

Input Constraints:

1 <= t <= 10

2 <= R <= 1000

2 <= C <= 1000

‘a’ <= map[i][j] <= ‘z’

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd

Sample Output:

1
2
3
4
0
3
2
2

思路

题意为求最少杀人数,如果周围的字母与当前所在位置字母相同,则可以直接走过去,如果不相同就需要杀掉一个守卫。那么可以用一个双端队列来维护当前所走路径。如果周围字母与当前字母相同,就推到队头,否则推到队尾。
不过在写这个题目时,发现有个地方跟以前我写搜索时有点不一样。那就是visit数组的应用,以前写搜索在将位置推入队列时直接将这个位置变为已访问状态,而这个题是当这个位置被拿出来使用时才变成已访问状态。这样做的好处在于,可能在某种情况下,其他位置先访问到终点时将终点变为不可访问后,最优位置就无法访问了,从而无法求得最优解,又学到一招qwq。

代码

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
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e3+10;

struct node{
int x,y,dep;
node(int x,int y,int dep):x(x),y(y),dep(dep){}
};

deque<node> qu;
int visit[MAXN][MAXN];
string str[MAXN];
int n,m;
int ans;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void BFS() {
memset(visit,0,sizeof(visit));
while(!qu.empty()) qu.pop_front();
qu.push_front(node(0,0,0));
// visit[0][0]=1;
int cnt=0;
while(!qu.empty()) {
node t=qu.front();qu.pop_front();

if(t.x==n-1&&t.y==m-1)

ans=min(ans,t.dep);

if(visit[t.x][t.y])continue;
visit[t.x][t.y]=1;
for(int i=0;i<4;i++) {
int tx=t.x+dx[i];
int ty=t.y+dy[i];


if(tx>=0&&tx<n&&ty>=0&&ty<m&&!visit[tx][ty]) {
if(str[tx][ty]==str[t.x][t.y])
qu.push_front(node(tx,ty,t.dep));

else
qu.push_back(node(tx,ty,t.dep+1));

}
}
}
}
int main() {
// freopen("in.txt","r",stdin);

ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n>>m;
ans=0x3f3f3f3f;
for(int i=0;i<n;i++)
cin>>str[i];
BFS();
cout<<ans<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------
0%