test/aoj/3138.test.cpp

View this file on GitHub
Last update: 2020-10-25 17:34:17+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3138

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3138

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

#define call_from_test
#include "../../tools/dice.cpp"
#include "../../tools/drop.cpp"
#undef call_from_test

int dp[100][200][200];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w;
  cin>>h>>w;
  vector<string> ss(h);
  for(int i=0;i<h;i++) cin>>ss[i];

  Die d;
  d.top()='1';
  d.bottom()='6';
  d.north()='5';
  d.south()='2';
  d.east()='3';
  d.west()='4';

  auto ds=makeDice(d);
  map<array<int, 6>, int> idx;
  for(int i=0;i<(int)ds.size();i++)
    idx[ds[i].fs]=i;

  memset(dp,0,sizeof(dp));
  using T = tuple<int, int, int>;
  queue<T> que;

  dp[idx[d.fs]][0][0]=1;
  que.emplace(idx[d.fs],0,0);

  while(!que.empty()){
    int k,i,j;
    tie(k,i,j)=que.front();que.pop();
    if(i==h-1 and j==w-1) drop("YES");
    d=ds[k];

    if(i+1<h){
      int ni=i+1,nj=j;
      Die nd(d);
      nd.roll('S');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(i-1>=0){
      int ni=i-1,nj=j;
      Die nd(d);
      nd.roll('N');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(j+1<w){
      int ni=i,nj=j+1;
      Die nd(d);
      nd.roll('E');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(j-1>=0){
      int ni=i,nj=j-1;
      Die nd(d);
      nd.roll('W');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }
  }

  drop("NO");
  return 0;
}

#line 1 "test/aoj/3138.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3138

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

#define call_from_test
#line 1 "tools/dice.cpp"

#line 3 "tools/dice.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T=int>
struct Die{
  array<T, 6> fs;
  int &top()   {return fs[0];}
  int &south() {return fs[1];}
  int &east()  {return fs[2];}
  int &west()  {return fs[3];}
  int &north() {return fs[4];}
  int &bottom(){return fs[5];}
  void roll(char c){
    //the view from above
    // N
    //W E
    // S
    string b("EWNSRL");
    int v[6][4]={{0,3,5,2},
                 {0,2,5,3},
                 {0,1,5,4},
                 {0,4,5,1},
                 {1,2,4,3},
                 {1,3,4,2}};
    for(int k=0;k<6;k++){
      if(b[k]!=c) continue;
      int t=fs[v[k][0]];
      fs[v[k][0]]=fs[v[k][1]];
      fs[v[k][1]]=fs[v[k][2]];
      fs[v[k][2]]=fs[v[k][3]];
      fs[v[k][3]]=t;
    }
  }
  using ll = long long;
  ll hash(){
    ll res=0;
    for(int i=0;i<6;i++) res=res*256+fs[i];
    return res;
  }
  bool operator==(const Die &d) const{
    for(int i=0;i<6;i++) if(fs[i]!=d.fs[i]) return 0;
    return 1;
  }
};

template<typename T>
vector<Die<T>> makeDice(Die<T> d){
  vector<Die<T>> res;
  for(int i=0;i<6;i++){
    Die t(d);
    if(i==1) t.roll('N');
    if(i==2) t.roll('S');
    if(i==3) t.roll('S'),t.roll('S');
    if(i==4) t.roll('L');
    if(i==5) t.roll('R');
    for(int k=0;k<4;k++){
      res.emplace_back(t);
      t.roll('E');
    }
  }
  return res;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/3138.test.cpp"
#undef call_from_test

int dp[100][200][200];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w;
  cin>>h>>w;
  vector<string> ss(h);
  for(int i=0;i<h;i++) cin>>ss[i];

  Die d;
  d.top()='1';
  d.bottom()='6';
  d.north()='5';
  d.south()='2';
  d.east()='3';
  d.west()='4';

  auto ds=makeDice(d);
  map<array<int, 6>, int> idx;
  for(int i=0;i<(int)ds.size();i++)
    idx[ds[i].fs]=i;

  memset(dp,0,sizeof(dp));
  using T = tuple<int, int, int>;
  queue<T> que;

  dp[idx[d.fs]][0][0]=1;
  que.emplace(idx[d.fs],0,0);

  while(!que.empty()){
    int k,i,j;
    tie(k,i,j)=que.front();que.pop();
    if(i==h-1 and j==w-1) drop("YES");
    d=ds[k];

    if(i+1<h){
      int ni=i+1,nj=j;
      Die nd(d);
      nd.roll('S');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(i-1>=0){
      int ni=i-1,nj=j;
      Die nd(d);
      nd.roll('N');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(j+1<w){
      int ni=i,nj=j+1;
      Die nd(d);
      nd.roll('E');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }

    if(j-1>=0){
      int ni=i,nj=j-1;
      Die nd(d);
      nd.roll('W');
      if(nd.bottom()==ss[ni][nj] and !dp[idx[nd.fs]][ni][nj]){
        dp[idx[nd.fs]][ni][nj]=1;
        que.emplace(idx[nd.fs],ni,nj);
      }
    }
  }

  drop("NO");
  return 0;
}