CodeForces 586D – Phillip and Trains [BFS]

点击打开codeforces题目链接

Mean

你正在玩一个手机游戏,游戏是这样的:有三条公路,你刚开始在最左边,每秒钟你可以往右移动一个,然后可以上下移动或者不动,之后这一秒每个火车都往左移动两个格。直到所有火车开走并且始终不发生碰撞你就赢了。问你能否赢。

Analyse

根据相对运动,相当于每次往右移动三个格,同时上下移动。判断每步是否可以走动,搜索即可。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 105;
P st;
int n, k, vis[3][maxn];
char s[3][maxn];

bool bfs() {
    memset(vis, false, sizeof(vis));
    queue<P> qu; qu.push(st);
    while(!qu.empty()) {
        int x = qu.front().first, y = qu.front().second; qu.pop();
        if(isupper(s[x][++y])) continue;
        if(y >= n) return true;
        for(int i = -1; i <= 1; ++i) {
            int xx = x + i, yy = y;
            if(xx < 0 || xx > 2) continue;
            if(isupper(s[xx][yy])) continue;
            if(isupper(s[xx][++yy])) continue;
            if(yy >= n) return true;
            if(isupper(s[xx][++yy])) continue;
            if(yy >= n) return true;
            if(!vis[xx][yy]) {
                vis[xx][yy] = true;
                qu.push(P(xx, yy));
            }
        }
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 0; i < 3; ++i) {
            scanf("%s", s[i]);
            if(s[i][0] == 's')
                st = P(i, 0);
        }
        puts(bfs() ? "YES" : "NO");
    }
    return 0;
}

欢迎留言