Codeforces Round #325 (Div. 2) D. Phillip and Trains BFS

D. Phillip and Trains文章地址https://www.yii666.com/article/754003.html网址:yii666.com<

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/586/problem/D

Description

The mobile application store has a new game called "Subway Roller".

The protagonist of the game Philip is located in one end of the tunnel and wants to get out of the other one. The tunnel is a rectangular field consisting of three rows and n columns. At the beginning of the game the hero is in some cell of the leftmost column. Some number of trains rides towards the hero. Each train consists of two or more neighbouring cells in some row of the field.网址:yii666.com

All trains are moving from right to left at a speed of two cells per second, and the hero runs from left to right at the speed of one cell per second. For simplicity, the game is implemented so that the hero and the trains move in turns. First, the hero moves one cell to the right, then one square up or down, or stays idle. Then all the trains move twice simultaneously one cell to the left. Thus, in one move, Philip definitely makes a move to the right and can move up or down. If at any point, Philip is in the same cell with a train, he loses. If the train reaches the left column, it continues to move as before, leaving the tunnel.

Your task is to answer the question whether there is a sequence of movements of Philip, such that he would be able to get to the rightmost column.

Codeforces Round #325 (Div. 2) D. Phillip and Trains BFS

Input

Each test contains from one to ten sets of the input data. The first line of the test contains a single integer t (1 ≤ t ≤ 10 for pretests and tests or t = 1 for hacks; see the Notes section for details) — the number of sets.

Then follows the description of t sets of the input data.文章来源地址:https://www.yii666.com/article/754003.html

The first line of the description of each set contains two integers n, k (2 ≤ n ≤ 100, 1 ≤ k ≤ 26) — the number of columns on the field and the number of trains. Each of the following three lines contains the sequence of n character, representing the row of the field where the game is on. Philip's initial position is marked as 's', he is in the leftmost column. Each of the k trains is marked by some sequence of identical uppercase letters of the English alphabet, located in one line. Distinct trains are represented by distinct letters. Character '.' represents an empty cell, that is, the cell that doesn't contain either Philip or the trains.

​​,C​i​​,即此题的初始分值、每分钟减少的分值、dxy做这道题需要花费的时间。

Output

For each set of the input data print on a single line word YES, if it is possible to win the game and word NO otherwise.文章来源地址https://www.yii666.com/article/754003.html

Sample Input

2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....

Sample Output

YES
NO

HINT

题意

在一个n*3的格子中有火车和人,人一开始在最左边,人的目标是走到最右边

每次人先往右走一步,然后可以选择往上,往下,或者不动。然后火车前进两格

要求火车和人不相撞,然后问你这个人可不可以走到最右边

题解:

我BFS的,因为火车每次得走两步,所以最多就50个图,我预先把50个图全部预处理出来

然后就直接bfs跑就好了

代码:

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std; string s[];
int Mp[][][];
int dy[]={,,-};
int vis[][];
struct node
{
int x,y,t;
};
queue<node> Q;
int main()
{
int t;scanf("%d",&t);
while(t--)
{
memset(Mp,,sizeof(Mp));
memset(vis,,sizeof(vis));
while(!Q.empty())Q.pop();
int a,b;
scanf("%d%d",&a,&b);
for(int i=;i<;i++)
cin>>s[i];
int len=s[].size();
node now;
for(int i=;i<;i++)
{
for(int j=;j<len;j++)
{
if(s[i][j]<='Z'&&s[i][j]>='A')
Mp[j][i][]=;
if(s[i][j]=='s')
{
now.x = j;
now.y = i;
now.t = ;
}
}
}
int TTT= ; for(int i=;i<=;i++)
{
for(int j=;j<;j++)
{
for(int k=;k<len;k++)
{
if(Mp[k][j][i-]==)
{
if(k->=)
{
TTT = i;
Mp[k-][j][i]=;
}
}
}
}
} int flag = ;
Q.push(now);
while(!Q.empty())
{
now = Q.front();
Q.pop();
if(now.x>=len-||now.t>=TTT)
{
printf("YES\n");
flag = ;
break;
}
for(int i=;i<;i++)
{
node next = now;
next.x += ;
if(Mp[next.x][next.y][next.t])
continue;
next.y += dy[i];
next.t = next.t+;
if(next.y<||next.y>=)
continue;
if(Mp[next.x][next.y][next.t-]||Mp[next.x][next.y][next.t])
continue;
if(vis[next.x][next.y])continue;
vis[next.x][next.y]=;
Q.push(next);
} }
if(flag==)
{
printf("NO\n");
}
}
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png