Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

type Point struct {
	x, y int
}

func main() {
	dx := []int{1, 0, -1, 0}
	dy := []int{0, -1, 0, 1}
	maze := make([][]rune, 30)
	for i := range maze {
		maze[i] = make([]rune, 30)
	}
	next := make([][]rune, 30)
	for i := range next {
		next[i] = make([]rune, 30)
	}
	check := make([][]int, 30)
	for i := range check {
		check[i] = make([]int, 30)
	}
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		W, _ := strconv.Atoi(buf[0])
		H, _ := strconv.Atoi(buf[1])
		if W == 0 && H == 0 {
			break
		}
		for i := 0; i < H; i++ {
			scanner.Scan()
			buf_ := scanner.Text()
			for j, v := range buf_ {
				maze[i][j] = v
			}
		}
		man := 0
		for i := 0; i < H; i++ {
			for j := 0; j < H; j++ {
				if maze[i][j] != '.' && maze[i][j] != 'X' && maze[i][j] != '#' {
					switch maze[i][j] {
					case 'E':
						maze[i][j] = 0
						man++
					case 'N':
						maze[i][j] = 1
						man++
					case 'W':
						maze[i][j] = 2
						man++
					case 'S':
						maze[i][j] = 3
						man++
					}
				}
			}
		}
		ans := -1
		for t := 0; t <= 180; t++ {
			if man == 0 {
				ans = t
				break
			}
			for i := 0; i < H; i++ {
				for j := 0; j < W; j++ {
					check[i][j] = 0x7FFFFFFF
				}
			}
			for i := 0; i < H; i++ {
				for j := 0; j < W; j++ {
					if maze[i][j] > 3 {
						continue
					}
					l := (maze[i][j] + 3) % 4
					for k := 0; k < 4; k++ {
						y := i + dy[l]
						x := j + dx[l]
						if 0 <= y && y < H && 0 <= x && x < W && (maze[y][x] == '.' || maze[y][x] == 'X') {
							maze[i][j] = l
							check[y][x] = min(check[y][x], int((l+2)%4))
							break
						}
						l = (l + 1) % 4
					}
				}
			}
			for i := 0; i < H; i++ {
				for j := 0; j < W; j++ {
					next[i][j] = maze[i][j]
				}
			}
			for i := 0; i < H; i++ {
				for j := 0; j < W; j++ {
					if maze[i][j] > 3 {
						continue
					}
					y := i + dy[maze[i][j]]
					x := j + dx[maze[i][j]]
					if 0 <= y && y < H && 0 <= x && x < W && check[y][x] == int((maze[i][j]+2)%4) {
						if maze[y][x] == '.' {
							next[y][x] = maze[i][j]
						} else if maze[y][x] == 'X' {
							man--
						}
						next[i][j] = '.'
					}
				}
			}
			for i := 0; i < H; i++ {
				for j := 0; j < W; j++ {
					maze[i][j]=next[i][j]
				}
			}
		}
		if ^ans != 0 {
			fmt.Println(ans)
		} else {
			fmt.Println("NA")
		}
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

C++: #include<iostream>
#include<vector>

struct P{
	int x, y;
};

struct Person{
	P pos;
	int angle;
};

int toAngleIndex(char angle_c){
	if(angle_c == 'E'){
		return 0;
	}else if(angle_c == 'N'){
		return 1;
	}else if(angle_c == 'W'){
		return 2;
	}else{
		return 3;
	}
	return -1;//該当なし
}


const int MAX_WIDTH = 30, MAX_HEIGHT = 30;
const P dp[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

int main(){
	int W, H;
	while(std::cin >> W >> H, W){

		char map[MAX_WIDTH][MAX_HEIGHT];
		std::vector<Person> people;

		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				char c;
				std::cin >> c;
				if('E' <= c && c <= 'W'){
					people.push_back({{j, i}, toAngleIndex(c)});
					map[j][i] = '.';
				}else{
					map[j][i] = c;
				}
			}
		}

		int t = 0;
		while(!people.empty()){
			// Step 1: 向きを変える
			int grassMap[MAX_WIDTH][MAX_HEIGHT];
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++){
					grassMap[j][i] = 0;
				}
			}
			for(auto person : people){
				grassMap[person.pos.x][person.pos.y]++;
			}

			std::vector<Person> _p1;
			for(auto person : people){
				int prev_angle = person.angle;
				P prev_pos = person.pos;

				bool canMove = false;
				for(int i=0;i<4;i++){
					int angle = (prev_angle + i + 3) % 4;
					P pos = {person.pos.x + dp[angle].x,
									 person.pos.y + dp[angle].y};
					if(0 <= pos.x && pos.x < W && 
						 0 <= pos.y && pos.y < H &&
						 map[pos.x][pos.y] != '#' &&
						 grassMap[pos.x][pos.y] == 0){
						_p1.push_back({prev_pos, angle});//向きだけ変える
						canMove = true;
						break;
					}
				}
		
				if(!canMove){
					_p1.push_back({prev_pos, prev_angle});
				}
			}
			people = _p1;

			// Step 2 移動させる
			// 誰が移動の権利を得るのか
			int winnerMap[MAX_WIDTH][MAX_HEIGHT];
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++){
					winnerMap[j][i] = -1;
				}
			}
	
			std::vector<Person> _p2, _p3;
			for(int i=0;i<people.size();i++){
				Person person = people[i];
				int angle = person.angle;
				P prev_pos = person.pos,
					pos = {prev_pos.x + dp[angle].x,
								 prev_pos.y + dp[angle].y};
				if(winnerMap[pos.x][pos.y] == -1){//暫定チャンピオン
					winnerMap[pos.x][pos.y] = i;
				}else{//魔物級の熾烈な争い
					int iChampionIndex = winnerMap[pos.x][pos.y];
					Person icp = people[iChampionIndex];
					if((prev_pos.x == pos.x + 1 && prev_pos.x > icp.pos.x) ||
						 prev_pos.y < icp.pos.y){
						winnerMap[pos.x][pos.y] = i;
					}
				}

				_p2.push_back({pos, angle});
			}

			for(int i=0;i<people.size();i++){
				Person person = people[i], personAfterMoving = _p2[i];
				P posAfterMoving = personAfterMoving.pos;
		
				if(winnerMap[posAfterMoving.x][posAfterMoving.y] == i){
					if(map[posAfterMoving.x][posAfterMoving.y] != 'X'){// あんたが一番(ゴールはしていませんが)
						_p3.push_back(personAfterMoving);
					}
				}else{
					_p3.push_back(person);
				}
			}

			people = _p3;

			t++;
			if(t > 180)break;
		}
	
		if(t <= 180){
			std::cout << t << std::endl;
		}else{
			std::cout << "NA" << std::endl;
		}
	}
}

C++: #include<iostream>
#include<set>
#include<map>
using namespace std;

typedef pair<int,int> P;

string id = "ENWS";

int dir(char a){
  for(int i=0;i<4;i++)if(a==id[i])return i;
  return -1;
}

int main(){
  int h,w;
  string grid[30];
  bool use[30][30];
  int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};

  while(cin >> w >> h && (w||h)){
    for(int i=0;i<h;i++)cin >> grid[i];

    int ans = 0;
    while(ans<=180){
      set<P> s;
      int num = 0;
      for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
	  int d = dir(grid[i][j]);
	  if(0<=d){
	    num++;
	    for(int k=-1;k<3;k++){
	      int dd = (d+k+4)%4;
	      int sy = i+dy[dd], sx = j+dx[dd];
	      if(sy<0 || sx<0 || h<=sy || w<=sx)continue;
	      if(grid[sy][sx] == '.' || grid[sy][sx] == 'X'){
		grid[i][j] = id[dd];
		s.insert(P(sy,sx));
		break;
	      }
	    }
	  }
	}
      }
      if(!num)break;

      for(int i=0;i<h;i++)
	for(int j=0;j<w;j++)use[i][j] = false;

      set<P>::iterator ite;
      for(ite=s.begin();ite!=s.end();ite++){
	int i=(*ite).first,j=(*ite).second;
	if(!use[i][j] && (grid[i][j] == '.' || grid[i][j] == 'X')){
	  for(int k=0;k<4;k++){
	    int sy = i+dy[k], sx = j+dx[k];
	    if(sy<0 || sx<0 || h<=sy || w<=sx || use[sy][sx])continue;
	    int d = dir(grid[sy][sx]);
	    if(d<0)continue;
	    int dd = (k+2)%4;
	    if(d==dd){
	      grid[sy][sx] = '.';
	      if(grid[i][j]!='X')grid[i][j] = id[d];
	      use[sy][sx] = true;
	      break;
	    }
	  }
	}
	use[i][j] = true;
      }
      ans++;
    }
    if(ans>180)cout << "NA\n";
    else cout << ans << endl;
  }
}