CFr 811 D. Vladik and Favorite Game ( Interactive, Ad hoc )

Problem - 811D - Codeforces

題意：
給一張地圖，有些是炸彈，走上去馬上死。
起點在左上角，目標是 'F'。
你可以上下左右移動，但是上和下的控制可能是反的，左右也是。
互動走到 F。
操作數不可超過 2 * N * M。

制約：
1 ≤ N, M ≤ 100
保證有至少一條路徑可以走到終點。

解法：
有至少一條路徑，那麼至少可以往右走或者往下走。
不失一般性假設可以往下走，那麼就走上啊下的就知道上下有沒有反。
除非在這上和下的路上有終點，不然一定有至少一個地方可以往右走。
找到他之後左啊右的就知道左右有沒有反。
剩下就是最短路徑預處理。

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

const int MAXN = 100;
const int MAXM = 100;

int N, M;
string G[ MAXN ];

int gx, gy;

void run( char dir, int &x, int &y ) {
  static int button = 0;
  while( ++button > 2 * N * M );
  cout << dir << endl;
  cin >> x >> y;
  if( x == -1 ) assert( 0 );
  --x, --y;
  if( x == gx and y == gy ) exit( 0 );
}

char rev( char dir, bool opp ) {
  if( opp ) {
    if( dir == 'L' ) dir = 'R';
    else if( dir == 'R' ) dir = 'L';
    else if( dir == 'U' ) dir = 'D';
    else if( dir == 'D' ) dir = 'U';
  }
  return dir;
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> G[ i ];
    for( int j = 0; j < M; ++j ) {
      if( G[ i ][ j ] == 'F' ) {
        gx = i, gy = j;
        break;
      }
    }
  }
  // !!! 1 ≤ N, M ≤ 100
  int x = 0, y = 0;
  if( N == 1 ) {
    run( 'R', x, y );
    if( x + y == 0 ) {
      while( G[ x ][ y ] != 'F' ) {
        run( 'L', x, y );
      }
    } else {
      while( G[ x ][ y ] != 'F' ) {
        run( 'R', x, y );
      }
    }
  } else if( M == 1 ) {
    run( 'D', x, y );
    if( x + y == 0 ) {
      while( G[ x ][ y ] != 'F' ) {
        run( 'U', x, y );
      }
    } else {
      while( G[ x ][ y ] != 'F' ) {
        run( 'D', x, y );
      }
    }
  }
  bool opp_lr = false, opp_ud = false;
  if( G[ x ][ y + 1 ] == '*' ) {
    run( 'D', x, y );
    if( x + y == 0 ) {
      opp_ud = true;
    } else {
      run( 'U', x, y );
    }
    while( G[ x ][ y + 1 ] == '*' ) {
      run( rev( 'D', opp_ud ), x, y );
    }
    int qq = x + y;
    run( 'R', x, y );
    if( x + y == qq ) {
      opp_lr = true;
    }
  } else {
    run( 'R', x, y );
    if( x + y == 0 ) {
      opp_lr = true;
    } else {
      run( 'L', x, y );
    }
    while( G[ x + 1 ][ y ] == '*' ) {
      run( rev( 'R', opp_lr ), x, y );
    }
    int qq = x + y;
    run( 'D', x, y );
    if( x + y == qq ) {
      opp_ud = true;
    }
  }
  static int vis[ MAXN ][ MAXM ];
  static int pre[ MAXN ][ MAXM ];
  static const int dx[] = { 0, 1, 0, -1 };
  static const int dy[] = { 1, 0, -1, 0 };
  string mov;
  string haha = "RDLU";
  {
    int sx = x, sy = y;
    queue< pair< int, int > > que;
    que.emplace( sx, sy );
    vis[ sx ][ sy ] = 1;
    while( not que.empty() ) {
      int p, q;
      tie( p, q ) = que.front();
      que.pop();
      if( p == gx and q == gy ) break;
      for( int di = 0; di < 4; ++di ) {
        int np = p + dx[ di ];
        int nq = q + dy[ di ];
        if( not ( 0 <= np and np < N and 0 <= nq and nq < M ) ) continue;
        if( G[ np ][ nq ] == '*' ) continue;
        if( vis[ np ][ nq ] ) continue;
        vis[ np ][ nq ] = 1;
        pre[ np ][ nq ] = di;
        que.emplace( np, nq );
      }
    }
    for( int p = gx, q = gy; not ( p == sx and q == sy ); ) {
      int dd = pre[ p ][ q ];
      mov += haha[ dd ];
      p -= dx[ dd ];
      q -= dy[ dd ];
    }
  }
  reverse( mov.begin(), mov.end() );
  for( int i = 0; i < mov.size(); ++i ) {
    if( mov[ i ] == 'L' or mov[ i ] == 'R' ) {
      run( rev( mov[ i ], opp_lr ), x, y );
    } else {
      run( rev( mov[ i ], opp_ud ), x, y );
    }
  }
  assert( 0 );
  return 0;
}