2020.08.07 J – MaratonIME goes to Mito

On MaratonIME’s first trip to Mito, a restaurant, our dearest friend Estrela displayed some trouble to walk streets with trees. Every time he walked close enough to one, something really bad happened to him.

To avoid further harm, he decided to split the sidewalk into three separate lanes called S, M and H, each one approximately one meter wide, being S the one close to the street, M the one in the middle and H the one next to the houses. You can think of the region where Estrela walks as a grid with 3 lines (the lanes S, M and H) and n columns. Estrela is placed at the beginning (meter 1) of the sidewalk and wants to walk to meter n, where Mito is located. He knows the location of all the trees on his path and wants you to tell him if he can make it there unharmed. In order to guarantee that Estrela will arrive at Mito safely, he must not walk over any of the eight cells adjacent to the trees neither on the cells where trees are located.

The positions of the trees are given ordered, in other words, if i < j, the i-th tree wont be further away from the column 1 than the j-th tree.

Estrela can start and finish his walk at any lane.

The figure exemplifies the second test case. The dashed path is the path chosen by Estrela.

Input
In the first line there are two integers n e m the distance that Estrela wants to walk and the number of trees.

Then m lines follow, in the i-th line there is an integer a i and a character c i, meaning the i-th tree is in the lane c i and in the column a i. It is guaranteed that, if 1 ≤ i < j ≤ m, then a i ≤ a j, and no two trees in the input have the same lane and column.
Limits
* 3 ≤ n ≤ 105.
* 1 ≤ m ≤ 104.
* 1 ≤ a i ≤ n e c 1 = S or M or H for all i.

Output
Print “Yes” (without quotes) if Estrela can get to Mito safe and sound or “No” if not.

Examples
Input
4 2
1 S
4 S

Output
Yes

Input
5 2
1 H
5 S

Output
Yes

题目大意：
就是问能不能从最左边走到最右边。
先输入n，和m。分别表示路的长度和障碍的数量。
输入m个道路上的障碍。
S表示障碍在最上面，M表示障碍在间，H表示障碍在下面
有障碍的位置，周围八个格都不能通过。

题目链接

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int i,n,m,x,f=1;
    char a[1000010];
    memset(a,'a',sizeof(a));
    scanf("%d %d",&n,&m);

    for(i=1;i<=m;i++){
        scanf("%d",&x);
        getchar();
        if(a[x]=='a')
        scanf("%c",&a[x]);
        else
            f=0;
    }

    for(i=1;i<=n;i++){
        if(f==0)
            break;
        if(a[i]=='H'){
            if(a[i+1]=='S'||a[i+2]=='S'||a[i+3]=='S')
            {
                f=0;
                break;
            }
        }
        if(a[i]=='S'){
            if(a[i+1]=='H'||a[i+2]=='H'||a[i+3]=='H'){
                f=0;
                break;
            }
        }
        if(a[i]=='M'){
            f=0;
            break;
        }
    }
    if(f){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_45828951/article/details/107873014