用Dijkstra写的~~（有大病）~~

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
int h, w, mat[35][35];
int tx, ty, die, dx, dy, vel[35][35];
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool vir[35][35];
struct node {
	int ti, tj, velue, fx; //横 纵 花费 方向
	operator< ( const node & up ) const {
		return up.velue < velue;
	}
};
priority_queue<node> q;
bool ok ( int x, int y ) {
	return x >= 1 && x <= h && y >= 1 && y <= w && mat[x][y] != 0;
}
void val1 ( int ax, int ay, int bx, int by, int qw ) {
	if ( vel[bx][by] + qw < vel[ax][ay] ) vel[ax][ay] = vel[bx][by] + qw;
	if ( qw == 0 ) q.push ( {ax, ay, vel[ax][ay], 1} );
	if ( qw == 1 ) q.push ( {ax, ay, vel[ax][ay], 3} );
	if ( qw == 5 ) q.push ( {ax, ay, vel[ax][ay], 4} );
}
void val2 ( int ax, int ay, int bx, int by, int qw ) {
	if ( vel[bx][by] + qw < vel[ax][ay] ) vel[ax][ay] = vel[bx][by] + qw;
	if ( qw == 0 ) q.push ( {ax, ay, vel[ax][ay], 2} );
	if ( qw == 1 ) q.push ( {ax, ay, vel[ax][ay], 4} );
	if ( qw == 5 ) q.push ( {ax, ay, vel[ax][ay], 3} );
}
void val3 ( int ax, int ay, int bx, int by, int qw ) {
	if ( vel[bx][by] + qw < vel[ax][ay] ) vel[ax][ay] = vel[bx][by] + qw;
	if ( qw == 0 ) q.push ( {ax, ay, vel[ax][ay], 3} );
	if ( qw == 1 ) q.push ( {ax, ay, vel[ax][ay], 2} );
	if ( qw == 5 ) q.push ( {ax, ay, vel[ax][ay], 1} );
}
void val4 ( int ax, int ay, int bx, int by, int qw ) {
	if ( vel[bx][by] + qw < vel[ax][ay] ) vel[ax][ay] = vel[bx][by] + qw;
	if ( qw == 0 ) q.push ( {ax, ay, vel[ax][ay], 4} );
	if ( qw == 1 ) q.push ( {ax, ay, vel[ax][ay], 1} );
	if ( qw == 5 ) q.push ( {ax, ay, vel[ax][ay], 2} );
}
void dij() {
	memset ( vel, inf, sizeof ( vel ) );
	memset ( vir, false, sizeof ( vir ) );
	vel[tx][ty] = 0;
	q.push ( { tx, ty, 0, die } );
	while ( q.size() ) {
		node x = q.top();
		q.pop();
		if ( vir[x.ti][x.tj] ) continue;
		vir[x.ti][x.tj] = true;
		
		for ( int i = 0; i < 4; i++ ) {
			int sx = x.ti + dir[i][0], sy = x.tj + dir[i][1];
			if ( !ok ( sx, sy ) ) continue;
			switch ( x.fx ) {
			case 1:
				if ( sx == x.ti ) {
					if ( sy == x.tj - 1 ) val1 ( sx, sy, x.ti, x.tj, 1 );
					if ( sy == x.tj + 1 ) val1 ( sx, sy, x.ti, x.tj, 5 );
				}
				if ( sx == x.ti + 1 ) val1 ( sx, sy, x.ti, x.tj, 0 );
				break;
			case 2:
				if ( sx == x.ti ) {
					if ( sy == x.tj - 1 ) val2 ( sx, sy, x.ti, x.tj, 5 );
					if ( sy == x.tj + 1 ) val2 ( sx, sy, x.ti, x.tj, 1 );
				}
				if ( sx == x.ti - 1 ) val2 ( sx, sy, x.ti, x.tj, 0 );
				break;
			case 3:
				if ( sy == x.tj ) {
					if ( sx == x.ti - 1 ) val3 ( sx, sy, x.ti, x.tj, 1 );
					if ( sx == x.ti + 1 ) val3 ( sx, sy, x.ti, x.tj, 5 );
				}
				if ( sy == x.tj - 1 ) val3 ( sx, sy, x.ti, x.tj, 0 );
				break;
			case 4:
				if ( sy == x.tj ) {
					if ( sx == x.ti - 1 ) val4 ( sx, sy, x.ti, x.tj, 5 );
					if ( sx == x.ti + 1 ) val4 ( sx, sy, x.ti, x.tj, 1 );
				}
				if ( sy == x.tj + 1 ) val4 ( sx, sy, x.ti, x.tj, 0 );
				break;
			}
		}
	}
}
int main () {
	cin >> h >> w;
	for ( int i = 1; i <= h; i++ ) {
		for ( int j = 1; j <= w; j++ ) {
			char t; cin >> t;
			if ( t == '.' ) mat[i][j] = 0;
			if ( t == '#' ) mat[i][j] = 1;
			if ( t == 'E' ) mat[i][j] = 2, tx = i, ty = j, die = 1;
			if ( t == 'W' ) mat[i][j] = 2, tx = i, ty = j, die = 2;
			if ( t == 'N' ) mat[i][j] = 2, tx = i, ty = j, die = 3;
			if ( t == 'S' ) mat[i][j] = 2, tx = i, ty = j, die = 4;
			if ( t == 'F' ) mat[i][j] = 3, dx = i, dy = j;
		}
	}
	dij();
	cout << vel[dx][dy] << endl;
	return 0;
}