Create a gist now

Instantly share code, notes, and snippets.

@dohatsutsu /test.cpp Secret
Created Dec 20, 2016

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int dy[]={ 0, 0, 1,-1};
int ey[]={-1, 0, 0,-1};
int ex_y[] ={4,4,3,3,2,2,1,1};
int ex_ny[]={2,1,1,2,3,4,3,4};
int ex_cost[8][4]={
{1,0,1,1},
{0,0,1,2},
{0,1,1,1},
{1,1,1,0},
{1,1,0,1},
{1,0,1,1},
{0,1,1,1},
{0,0,2,1}
};
struct state{
int x,y;
int p[4];
};
int n;
string str;
bool t[5][32];
int visited[500][32][11][11][11][11];
state start;
bool solve(){
queue<state> Q;
start.x=1;
for(int i=1;i<=4;i++){
start.y=i;
Q.push(start);
visited[i][1][start.p[0]][start.p[1]][start.p[2]][start.p[3]]=true;
}
while(!Q.empty()){
state s=Q.front(),next;
Q.pop();
if(s.x==n+1)return true;
for(int i=0;i<4;i++){
int ty=s.y+ey[i];
int tx=s.x;
if(s.p[i]==0)continue;
if(t[ty][tx])continue;
next=s;
next.p[i]=s.p[i]-1;
next.x=s.x+1;
next.y=s.y+dy[i];
int *vd=&visited[next.y][next.x][next.p[0]][next.p[1]][next.p[2]][next.p[3]];
if(*vd)continue;
*vd=true;
Q.push(next);
}
if(t[1][s.x]||t[2][s.x]||t[3][s.x])continue;
for(int i=0;i<8;i++){
if(s.y!=ex_y[i])continue;
next=s;
int j;
for(j=0;j<4;j++){
next.p[j]-=ex_cost[i][j];
if(next.p[j]<0)break;
}
if(j<4)continue;
next.y=ex_ny[i];
next.x++;
int *vd=&visited[next.y][next.x][next.p[0]][next.p[1]][next.p[2]][next.p[3]];
if(*vd)continue;
*vd=true;
Q.push(next);
}
}
return false;
}
void init(){
for(int i=0;i<5;i++){
for(int j=0;j<32;j++)t[i][j]=true;
}
}
int main(){
while(cin>>n&&n){
init();
for(int i=3;i>=1;i--){
cin>>str;
for(int j=1;j<=n;j++){
t[i][j]=(str[j-1]=='X');
}
}
for(int i=0;i<4;i++)cin>>start.p[i];
cout<<(solve()?"Yes":"No")<<endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment