The Fault in Our Cubes Gym - 101257A (dfs)-白红宇

The Fault in Our Cubes Gym - 101257A (dfs)

阅读量：4204 次

发布时间：2019-05-26

本文共 3980 字，大约阅读时间需要 13 分钟。

Rula is the Human Resources Manager at Mixed Dimensions Inc. She has some very delightful puzzles for the employees to enjoy their free time at the office. One of these puzzles is the Worm Puzzle.

$\text{[math]}$

The puzzle consists of 27 cubic pieces of several types. The pieces are connected by a rope that runs through holes in the pieces, and allows the pieces to rotate. In order to solve the puzzle, you need to build a 3x3x3 cube.

Each piece has one of the following three types:

$\text{[math]}$

Type E represents an end cube, it has a hole at one face only. This piece is always connected to only one other piece.

Type I represents a cube which has two holes on opposite faces, the rope goes straight into one hole and out through the other.

Type L represents a cube which has two holes in two adjacent faces, the rope enters through one face, makes a 90 degree turn, and exits through the other face.

Well, Hasan has cut the rope of the puzzle by mistake, of course he didn’t want to tell Rula about it, so he bought a new rope and linked the pieces together to make a new Worm Puzzle, but he wasn't sure whether he linked them in their original order or not.

Now Rula has been trying to solve the puzzle for two days, but with no success, although she used to solve it in 30 seconds. She started to suspect that something might be wrong with the puzzle.

She asked one of the engineers at Mixed Dimensions to verify whether the puzzle is solvable or not. Unfortunately, that engineer was Hasan, and of course, the question is difficult for him to answer.

Given the type of each piece, and the order in which Hasan linked the pieces together, can you help him by finding whether the given puzzle is solvable or not?

Input

The input consists of a string of 27 letters, each letter will be either an E, I, or L, which represents the type of that piece.

The first and last letters are always E.

Output

Print YES if the given puzzle is solvable, otherwise print NO.

Example

Input

EILILLLLLLILILLLLLLILILLLLE

Output

YES

Input

EILLLILLILLLILILLLLILILILIE

Output

YES

Input

EILLILLLILLILLLILLLILLLLILE

Output

Rula是Mixed Dimensions Inc.的人力资源经理。她有一些非常愉快的谜题让员工在办公室享受自由时间。这些难题之一是蠕虫拼图。

拼图由27个立方体的几种类型。这些部件通过穿过部件中的孔的绳索连接，并允许部件旋转。为了解决这个难题，你需要建立一个3x3x3的立方体。

每个部件具有以下三种类型之一：

类型E表示端部立方体，其仅在一个面具有孔。这部分总是只连接到一个其他部分。

类型I表示在相对面上具有两个孔的立方体，绳索直接进入一个孔并且通过另一个孔。

类型L表示在两个相邻面中具有两个孔的立方体，绳索通过一个面进入，进行90度转弯，并且通过另一个面退出。

好吧，哈桑错误地切断了谜题的绳子，当然他不想告诉罗拉它，所以他买了一条新绳子，把它们连接起来制作一个新的蠕虫拼图，但他不确定无论他们是否按原来的顺序把它们联系起来。

现在Rula一直在试图解决这个难题两天，但没有成功，虽然她曾经在30秒内解决它。她开始怀疑一些东西可能是错误的拼图。

她要求“混合维度”中的一个工程师来验证拼图是否可以解决。不幸的是，那位工程师是哈桑，当然，这个问题很难让他回答。

鉴于每件作品的类型，以及哈桑将作品连接在一起的顺序，你能帮助他通过找到给定的谜题是否可解决？

输入

输入由27个字母的字符串组成，每个字母将是一个E，I或L，它代表该片段的类型。

第一个和最后一个字母总是E.

输出

如果给定的拼图是可解决的，则打印YES，否则打印NO。

例

输入

EILILLLLLILILLLLLLILILLLLE

输出

是

输入

EILLLILLILLLILILLLLILILILIE

输出

是

输入

EILLILLLILLILLLILLLLLLLE

输出

没有

////  main.cpp//  160929////  Created by liuzhe on 16/9/29.//  Copyright © 2016年 my_code. All rights reserved.////#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   using namespace std;char s[28];int dx[6]={0,0,1,-1,0,0};int dy[6]={0,1,0,0,-1,0};int dz[6]={1,0,0,0,0,-1};int vis[6][6][6];int flag = 0;#define T (x<1)||(x>3)||(y<1)||(y>3)||(z<1)||(z>3)void dfs(int x,int y,int z,int id,int step,int dir){ if(flag) return ; if(T) return ; if(vis[x][y][z]) return ; vis[x][y][z] = 1; step++; if(step == 27) {flag = 1;return ;} if(s[id]=='E') dfs(x+dx[0],y+dy[0],z+dz[0],id+1,step,0); else if(s[id]=='I') dfs(x+dx[dir],y+dy[dir],z+dz[dir],id+1,step,dir); else for(int i=0;i<6;i++) if(dir!=i&&dir+i!=5) dfs(x+dx[i],y+dy[i],z+dz[i],id+1,step,i); vis[x][y][z] = 0; return ;}int f(){ for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++) { dfs(i,j,k,0,0,0); if(flag) return 1; } return 0;}int main(){ scanf("%s",s); memset(vis,0,sizeof(vis)); flag = 0; if(f()) puts("YES"); else puts("NO"); return 0;}