UVA 10818 - Dora Trip ( DP, bitmask )

UVa Online Judge

題意：
給一個 R * C 的圖，保證周圍都是牆( # )，也不能拜訪 ( X )，起點在 ( S )，問在拜訪最多 ( * ) 的前提下，最短迴路的最小字典序序列序列是什麼。

資料規模：
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.

解法：
就是個臭臭長長的動態規劃，因為寶物不能拿兩次，用 bitmask 描述。注意要字典序最小，所以更新的時候優先用字典序小的方向更新，最後暴力把所有最短的路徑復原後比較即可。

時間 / 空間複雜度：
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;
}