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 <cstdio>
#include <vector>
#include <utility>
#include <set>

using namespace std;

char** map;
int w,h;

int n;
int nn[4][2];
char d[4];

void Init(){
	d[1] = 'N';
	d[2] = 'W';
	d[3] = 'S';
	d[0] = 'E';
	nn[0][0] = 1;nn[0][1] = 0;
	nn[1][0] = 0;nn[1][1] = -1;
	nn[2][0] = -1;nn[2][1] = 0;
	nn[3][0] = 0;nn[3][1] = +1;
}

class Person;

Person* Find(pair<int,int> p);

class Person{
public:
	int X,Y;
	char Direction;
	bool Clear;
	
	Person(){
		Clear = false;
	}
	bool Check(int x,int y){
		if(x < 0 || y < 0){ return false; }
		if(x >= w || y >= h){ return false; }
		if(map[x][y] == '#'){ return false; }
		pair<int,int> p;
		p.first = x;
		p.second = y;
		if(Find(p) != NULL){ return false; }
		return true;
	}
	pair<int,int> GetFront(){
		pair<int,int> res;
		res.first = X;
		res.second = Y;
		switch(Direction){
			case 'N':
				n = 1;
				break;
			case 'W':
				n = 2;
				break;
			case 'S':
				n = 3;
				break;
			case 'E':
				n = 0;
				break;
		}
		res.first += nn[n % 4][0];
		res.second += nn[n % 4][1];
		

		return res;
	}
	void Move(){
	
		
		switch(Direction){
			case 'N':
				n = 4;
				break;
			case 'W':
				n = 5;
				break;
			case 'S':
				n = 6;
				break;
			case 'E':
				n = 3;
				break;
		}
		for(int i=0;i<4;i++){
			//printf("%i::%c:%+d,%+d\n",i,Direction,nn[(i + n) % 4][0],nn[(i + n) % 4][1]);
			if(Check(X + nn[(i + n) % 4][0],Y + nn[(i + n) % 4][1])){
				Direction = d[(i + n) % 4];
				//printf("->%c\n",Direction);
				break;
			}
		}
	}
};


vector<Person> people;
set< pair<int,int> > points;


Person* Find(pair<int,int> p){
	vector<Person>::iterator pit;
	
	for(pit = people.begin();pit<people.end();pit++){
		if((*pit).Clear == false && p.first == (*pit).X && p.second == (*pit).Y){
			return &(*pit);
		}
	}
	return NULL;
}

class Solve{
	public:
	
	void NewMap(){
		map = new char*[w];
		for(int i=0;i<w;i++){
			map[i] = new char[h];
		}
	}
	void DeleteMap(){
		for(int i=0;i<w;i++){
			delete[] map[i];
		}
		delete[] map;
	}
	
	
	
	void Run(){
		char c;
		int time;
		while(scanf("%d %d",&w,&h) && w && h){
			//printf("%d:%d\n",w,h);
			people.clear();
			NewMap();
			
			
			
			for(int j = 0;j < h;j++){
				for(int i = 0;i < w;i++){
					while(1){
						scanf("%c",&c);
						if(c != '\n'){break;}
					}
					if(c == '#'){
						map[i][j] = '#';
					}else if(c == 'X'){
						map[i][j] = 'X';
						
					}else{
						map[i][j] = '.';
						if(c != '.'){
							Person per;
							per.X = i;
							per.Y = j;
							per.Direction = c;
							people.push_back(per);
						}
					}
				}
			}
			
			time = 0;
			bool res = false;
			while(time <= 120){
				vector<Person>::iterator pit;
			
				points.clear();
			
				bool flag = true;
				for(pit = people.begin();pit<people.end();pit++){
					if((*pit).Clear){ continue; }
					flag = false;
					(*pit).Move();
					pair<int,int> p = (*pit).GetFront();
					//printf("(%d,%d),%c -> (%d,%d)\n",(*pit).X,(*pit).Y,(*pit).Direction,p.first,p.second);
					if((*pit).Check(p.first,p.second)){
						points.insert(p);
					}
				}
				if(flag){
					res = true;
					break;
				}
				
				time++;
			
				set< pair<int,int> >::iterator poit;
			
				for(poit = points.begin();poit != points.end();poit++){
					//printf("FIND To (%d,%d)\n",(*poit).first,(*poit).second);
					for(int i=0;i<4;i++){
						pair<int,int> pp;
						pp.first = (*poit).first + nn[i][0];
						pp.second = (*poit).second + nn[i][1];
						//printf("(%d,%d)\n",pp.first,pp.second);
						Person* ps = Find(pp);
						if(ps != NULL){
							if((*ps).GetFront() != (*poit)){
								//printf("NO\n");
								continue;
							}
							pp = (*ps).GetFront();
							//printf("(%d,%d)->(%d,%d)\n",(*ps).X,(*ps).Y,pp.first,pp.second);
							(*ps).X = pp.first;
							(*ps).Y = pp.second;
							
							if(map[(*ps).X][(*ps).Y] == 'X'){
								(*ps).Clear = true;
							}
							break;
						}
					}
				}
				
				/*
				char dm[20][20];
				for(int j = 0;j < h;j++){
					for(int i = 0;i < w;i++){
						dm[i][j] = map[i][j];
					}
				}
				for(pit = people.begin();pit<people.end();pit++){
					if((*pit).Clear){ continue; }
					dm[(*pit).X][(*pit).Y] = (*pit).Direction;
				}
				for(int j = 0;j < h;j++){
					for(int i = 0;i < w;i++){
						printf("%c",dm[i][j]);
					}
					printf("\n");
				}	
				printf("\n");
				*/
			}
			if(res){
				printf("%d\n",time);
			}else{
				printf("NA\n");
			}
			DeleteMap();
		}
	}
};

int main(){
	Init();
	Solve s;
	s.Run();
	return 0;
}