CodeForces - 585B

人每秒必须向右走一格,可以选择上下走一格或不动。火车每秒向左走两格,小人是否能通过隧道

让小人先右走一格,再上下移动,再右两格。这样就只有小人动火车不动了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2.2e6;
int n, k;
char s[3][2333];
bool vis[3][2333];
int bfs(int sy)
{
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int>> q;
    q.push(make_pair(sy, 0));
    vis[sy][0] = 1;
    while (!q.empty())
    {
        pair<int, int> now;
        now = q.front();
        q.pop();
        if (now.second >= n - 1)
            return puts("YES");
        if (s[now.first][now.second + 1] == '.')
        {
            if (vis[now.first][now.second + 3] == 0 && s[now.first][now.second + 2] == '.' && s[now.first][now.second + 3] == '.')
                q.push(make_pair(now.first, now.second + 3)), vis[now.first][now.second + 3] = 1;//, printf("%d %d\n", now.first, now.second + 3);
            if (now.first < 2 && vis[now.first + 1][now.second + 3] == 0 && s[now.first + 1][now.second + 1] == '.' && s[now.first + 1][now.second + 2] == '.' && s[now.first + 1][now.second + 3] == '.')
                q.push(make_pair(now.first + 1, now.second + 3)), vis[now.first + 1][now.second + 3] = 1;// printf("%d %d\n", now.first + 1, now.second + 3);
            if (now.first > 0 && vis[now.first - 1][now.second + 3] == 0 && s[now.first - 1][now.second + 1] == '.' && s[now.first - 1][now.second + 2] == '.' && s[now.first - 1][now.second + 3] == '.')
                q.push(make_pair(now.first - 1, now.second + 3)), vis[now.first - 1][now.second + 3] = 1;// printf("%d %d\n", now.first - 1, now.second + 3);
        }
    }
    return puts("NO");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 2333; j++)
                s[i][j] = '.';
        for (int i = 0; i < 3; i++)
            scanf("%s", s[i]);
        s[0][n] = s[1][n] = s[2][n] = '.';
        for (int i = 0; i < 3; i++)
            if (s[i][0] == 's')
                bfs(i);
    }
}