AOJ0210 ザ・スクエアーズ

解法

---

誤読していた。向きを変えるので1秒、動こうとするので1秒とかやって訳の分からないことをしていた。
向きを変えるステップは自明なので簡単だが、移動するステップが面倒。
最初人視点でやっていたので詰んでしまったが、マス視点でやってあとは頑張った。
dxとかdyとかdmとか4次元配列になってるけど、これはただ求める計算式に至らなかっただけ。
良い感じにシュミレーションすれば勝てる。

ソース

---

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
#define fr first
#define sc second
const int dy[][4] = {{1,0,-1,0},{0,-1,0,1},{-1,0,1,0},{0,1,0,-1}};
const int dx[][4] = {{0,1,0,-1},{1,0,-1,0},{0,-1,0,1},{-1,0,1,0}};
const int dm[][4] = {{3,0,1,2},{0,1,2,3},{1,2,3,0},{2,3,0,1}};
const int my[] = { 0, -1, 0, 1}, mx[] = { 1, 0, -1, 0};
const int md[] = { 2, 3, 0, 1};
int w, h;
char mas[30][30];
vector< Pii > vc;
string tmp = "ENWS";
int search( int y , int x){
  for(int i = 0 ; i < vc.size() ; i++ ){
    if(Pi(y,x) == vc[i].sc){
      return i;
    }
  }
  return -1;
}
vector< Pii >  solve(){
  vector< Pii > java;
  for(int i = 0 ; i < vc.size() ; i++ ){
    //change
    for(int j = 0 ; j < 4 ; j++ ){
      int yy = vc[i].sc.fr + dy[vc[i].fr][j];
      int xx = vc[i].sc.sc + dx[vc[i].fr][j];
      if(mas[yy][xx] != '#' && search(yy,xx) == -1){
        vc[i].fr = dm[vc[i].fr][j];
        break;
      }
    }
  }
  //push
  bool list[1000] = {};
  for(int i = 0 ; i < h ; i++ ){
    for(int j = 0 ; j < w ; j++ ){
      if(mas[i][j] == '#' || search(i,j) != -1) continue;
      for(int k = 0 ; k < 4 ; k++ ){
        int ny = i + my[k], nx = j + mx[k], iti;
        if((iti = search(ny,nx)) == -1) continue;
        if(vc[iti].fr == md[k]){
          if(mas[i][j] != 'X') java.push_back(Pii(vc[iti].fr,Pi(i,j)));
          list[iti] = true;
          break;
        }
      }
    }
  }
  for(int i = 0 ; i < vc.size() ; i++ ){
    if(!list[i]) java.push_back(vc[i]);
  }
  return java;
}
int main(){
  while(cin >> w >> h , w){
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
        if(tmp.find(mas[i][j]) != string::npos){
          vc.push_back(Pii( tmp.find(mas[i][j]), Pi( i, j)));
        }
      }
    }
    int ret = 0;
    while(ret <= 180 && !vc.empty()){
      vc = solve();
      ret++;
    }
    if(ret == 181) cout << "NA" << endl;
    else cout << ret << endl;
    vc.clear();
  }
}