# UVA 10818 - Dora Trip ( DP, bitmask )

UVa Online Judge

The input file contains no more than 20 test cases. The details of each set are given as follows:
The first line of each case contains two integers r and c (1 ≤ r, c ≤ 20), which are the number of
rows and columns of the map respectively. The next r lines, each with c characters, give the map itself.
For each character, a space ‘ ’ stands for an open space; a hash mark ‘#’ stands for an obstructing wall;
the capital letter ‘S’ stands for the position of Nobita’s house, which is where his journey is to start
and end; the capital letter ‘X’ stands for a dangerous place; and an asterisk ‘*’ stands for a place he has
to visit. The perimeter of the map is always closed, i.e., there is no way to get out from the coordinate
of the ‘S’. The number of places that Nobita has to visit is at most 10.
The input file is terminated by a null case where r = c = 0. This case should not be processed.

O( N^2 * 2^10 )

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

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v; return 1;
}

const int dx[] = { 0, -1, 1, 0 };
const int dy[] = { 1, 0, 0, -1 };

int dp[ 20 ][ 20 ][ 1 << 10 ];
tuple< int, int, int > pre[ 20 ][ 20 ][ 1 << 10 ];

map< pair< int, int >, int > mp;
int id( int x, int y ){
if( mp.count( make_pair( x, y ) ) ){
return mp[ make_pair( x, y ) ];
}
int size = mp.size();
return mp[ make_pair( x, y ) ] = size;
}

#define short myshort

signed main(){
ios::sync_with_stdio( 0 );
int N, M;
string buff;
while( getline( cin, buff ) ){
{
stringstream ss( buff );
ss >> N;
ss >> M;
if( N + M == 0 ){
break;
}
}
vector< string > G( N );
for( int i = 0; i < N; ++i ){
getline( cin, G[ i ] );
}
mp.clear();
memset( dp, 0x3f3f3f3f, sizeof( dp ) );
queue< tuple< int, int, int, int > > que;
int sx, sy;
for( int i = 0; i < N; ++i ){
for( int j = 0; j < M; ++j ){
if( G[ i ][ j ] == 'S' ){
que.emplace( dp[ i ][ j ][ 0 ] = 0, sx = i, sy = j, 0 );
}
}
}
while( not que.empty() ){
int d, x, y, t; tie( d, x, y, t ) = que.front(); que.pop();
for( int di = 0; di < 4; ++di ){
int nx = x + dx[ di ];
int ny = y + dy[ di ];
assert( 0 <= nx and nx < N and 0 <= ny and ny < M );
if( G[ nx ][ ny ] == 'X' or G[ nx ][ ny ] == '#' ) continue;
if( G[ nx ][ ny ] == ' ' or G[ nx ][ ny ] == 'S' ){
if( upmin( dp[ nx ][ ny ][ t ], d + 1 ) ){
que.emplace( d + 1, nx, ny, t );
pre[ nx ][ ny ][ t ] = make_tuple( x, y, t );
}
} else{
if( upmin( dp[ nx ][ ny ][ t | 1 << id( nx, ny ) ], d + 1 ) ){
que.emplace( d + 1, nx, ny, t | 1 << id( nx, ny ) );
pre[ nx ][ ny ][ t | 1 << id( nx, ny ) ] = make_tuple( x, y, t );
}
}
}
}
vector< int > best_t;
int maxv = 0, short = 0x3f3f3f3f;
for( int t = 0; t < 1 << 10; ++t ){
if( dp[ sx ][ sy ][ t ] == 0x3f3f3f3f ) continue;
int tc = __builtin_popcount( t );
if( maxv < tc ){
maxv = tc;
short = dp[ sx ][ sy ][ t ];
best_t = vector< int >( 1, t );
} else if( maxv == tc ){
if( short > dp[ sx ][ sy ][ t ] ){
short = dp[ sx ][ sy ][ t ];
best_t = vector< int >( t );
} else{
best_t.emplace_back( t );
}
}
}
if( maxv == 0 ){
cout << "Stay home!\n";
} else{
string ans;
for( int f = 0; f < best_t.size(); ++f ){
string mov;
for( int i = sx, j = sy, t = best_t[ f ]; ; ){
int pi, pj, pt;
tie( pi, pj, pt ) = pre[ i ][ j ][ t ];
if( i - pi == 1 ) mov += "S";
else if( i - pi == -1 ) mov += "N";
else if( j - pj == 1 ) mov += "E";
else mov += "W";
tie( i, j, t ) = pre[ i ][ j ][ t ];
if( i == sx and j == sy and t == 0 ) break;
}
reverse( mov.begin(), mov.end() );
if( ans.empty() or mov < ans ){
ans = mov;
}
}
cout << ans << "\n";
}
}
return 0;
}
```