0-1BFS

$\text{0-1BFS}$本质上是一种特殊的图,它的边权有$1$和$0$两种。同时为了保持$BFS$状态单调的特性,使用0权头入、1权尾入的入队方式。

$1$ SP22393 KATHTHI - KATHTHI

给出一个$n \times m$的网格,每个位置有一个小写字母,初始在$(1, 1)$,每次可以向上下左右走,问走到$(n, m)$的最小花费
设$(x, y)$为当前位置,$(nx, ny)$为下一位置。$s[x][y]$表示$(x, y)$位置的字符。
若$s[x][y] = s[nx][ny]$,则移动的花费为0,否则花费为1

sb题。

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
#define MAXN 2020
#define mkp make_pair

int dx[4] = {1, 0, -1, 0} ;
int dy[4] = {0, 1, 0, -1} ;
using namespace std ; deque <pair<int, int>> q ;
int T, N, M, i, j, dis[MAXN][MAXN] ; char base[MAXN][MAXN] ;

inline void bfs(){
memset(dis, 63, sizeof(dis)) ;
dis[1][1] = 0 ; q.push_front(mkp(1, 1)) ;
while (!q.empty()){
int x = q.front().first, y = q.front().second ; q.pop_front() ;
for (i = 0 ; i < 4 ; ++ i) {
register int kx = x + dx[i], ky = y + dy[i] ;
if (kx < 1 || kx > N || ky < 1 || ky > M) continue ;
if (dis[kx][ky] > dis[x][y] + (base[x][y] != base[kx][ky]))
dis[kx][ky] = dis[x][y] + (base[x][y] != base[kx][ky]),
(base[x][y] == base[kx][ky]) ? q.push_front(mkp(kx, ky)) : q.push_back(mkp(kx, ky)) ;
}
}
}
int main(){
cin >> T ;
while (T --){
scanf("%d%d", &N, &M) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
cin >> base[i][j] ;
bfs() ; cout << dis[N][M] << endl ;
}
}

$2$ CF1063B Labyrinth

你正在玩一款电脑游戏。
在其中一关,你位于一个 n行 m 列的迷宫。每个格子要么是可以通过的空地,要么是障碍。迷宫的起点位于第 r 行第 c列。你每一步可以向上、下、左、右中的一个方向移动一格,前提是那一格不是障碍。你无法越出迷宫的边界.
不幸的是,你的键盘快坏了,所以你只能向左移动不超过x格,并且向右移动不超过 y格。因为上下键情况良好,所以对向上和向下的移动次数没有限制。现在你想知道在满足上述条件的情况下,从起点出发,有多少格子可以到达(包括起点)?


嗯,一道很好的题。其实就是考虑我们如果从$(x,y)$出发,到达$(ex,ey)$,向右步数越少向左部署就越少(操作互相抵消)。

所以直接左右移动的边权设置为1,上下设置为0,跑BFS即可。观察这样做的合理性:只有左右有限制,所以最后对于每个点check一下就好。

不知道是不是因为网格图,SPFA在这种题上疯狂fst。。233

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
pair <int, int> now ;
int N, M ; char In[MAXN] ;
int dx[4] = {0, 1, 0, -1} ;
int dy[4] = {1, 0, -1, 0} ;//
deque <pair<int, int>> q ; int ans, i, j ;
bool map[MAXN][MAXN] ; int dis[MAXN][MAXN], L, R, sx, sy ;

inline void bfs(){
memset(dis, 63, sizeof(dis)) ;
dis[sx][sy] = 0 ; q.push_front(mkp(sx, sy)) ;
while (!q.empty()){
now = q.front() ; q.pop_front() ;
for (i = 0 ; i < 4 ; ++ i){
int kx = now.first + dx[i], ky = now.second + dy[i] ;
if (kx < 1 || ky < 1 || kx > N || ky > M || !map[kx][ky]) continue ;
if (dis[kx][ky] > dis[now.first][now.second] + (i == 2))
dis[kx][ky] = dis[now.first][now.second] + (i == 2),
(i != 2) ? q.push_front(mkp(kx, ky)) : q.push_back(mkp(kx, ky)) ;
}
}
}
int main(){
cin >> N >> M >> sx >> sy >> L >> R ;
for (i = 1 ; i <= N ; ++ i){
cin >> (In + 1) ;
for (j = 1 ; j <= M ; ++ j)
if (In[j] == '.') map[i][j] = 1 ;
}
bfs() ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j){
if (dis[i][j] < 0) continue ;
if (dis[i][j] <= L && j - sy + dis[i][j] <= R) ++ ans ;
}
cout << ans << endl ; return 0 ;
}

诶,又水一篇文章诶qwq。