CFR 374 C. Inna and Dima ( DP )

Problem - C - Codeforces

題意：
給一個只由 "DIMA" 中的字符組成的 N * M 的矩陣。有個人要重複以下過程：
1. 先選一個 'D' 的格子，在滿足條件而可以移動的前提下進行：
2. 移動到上下左右的其中一格 'I'
3. 移動到上下左右的其中一格 'M'
4. 移動到上下左右的其中一格 'A'
5. 移動到上下左右的其中一格 'D'
6. 從 2. 重新進行
求最多可以走幾次完整的 "DIMA"，若無限多，輸出 "Poor Inna!"，若為 0，輸出 "Poor Dima!"，若有限則輸出數量。

資料規模：
行數 1 ≤ N ≤ 1e3
列數 1 ≤ M ≤ 1e3
TL: 1000 ms
ML: 256 MB

解法：
dp[ i ][ j ]：以 ( i, j ) 開始最多可以走多少 "DIMA"。( 不限 G[ i ][ j ] 是否為 'D' )
亂 dfs 就可以了。( 真隨便的說明真不好意思，看看代碼吧 )
如果能 dfs 到祖先就代表有環，直接輸出無限多解後結束程序。

時間 / 空間複雜度：
O( N * M )

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

int N, M;
vs G;

void init(){
  cin >> N >> M;
  G = vs( N );
  for( int i = 0; i < N; ++i ){
    cin >> G[ i ];
  }
}

vvi dp;
vvi visiting;

void dfs( int x, int y ){
  if( visiting[ x ][ y ] ){
    cout << "Poor Inna!" << endl;
    exit( 0 );
  }
  if( dp[ x ][ y ] != -1 ) return;
  visiting[ x ][ y ] = 1;
  dp[ x ][ y ] = G[ x ][ y ] == 'A';
  for( int di = 0; di < 4; ++di ){
    int nx = x + dx[ di ];
    int ny = y + dy[ di ];
    if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue;
    if( G[ x ][ y ] == 'D' and G[ nx ][ ny ] == 'I' ){
      dfs( nx, ny );
      upmax( dp[ x ][ y ], dp[ nx ][ ny ] );
    }
    if( G[ x ][ y ] == 'I' and G[ nx ][ ny ] == 'M' ){
      dfs( nx, ny );
      upmax( dp[ x ][ y ], dp[ nx ][ ny ] );
    }
    if( G[ x ][ y ] == 'M' and G[ nx ][ ny ] == 'A' ){
      dfs( nx, ny );
      upmax( dp[ x ][ y ], dp[ nx ][ ny ] );
    }
    if( G[ x ][ y ] == 'A' and G[ nx ][ ny ] == 'D' ){
      dfs( nx, ny );
      upmax( dp[ x ][ y ], dp[ nx ][ ny ] + 1 );
    }
  }
  visiting[ x ][ y ] = 0;
}

void preprocess(){
  dp = vvi( N, vi( M, -1 ) );
  visiting = vvi( N, vi( M ) );
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < M; ++j ){
      if( dp[ i ][ j ] != -1 ) continue;
      if( G[ i ][ j ] != 'D' ) continue;
      dfs( i, j );
    }
  }
}

void solve(){
  int ans = 0;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < M; ++j ){
      upmax( ans, dp[ i ][ j ] );
    }
  }
  if( ans == 0 ){
    cout << "Poor Dima!" << endl;
  } else{
    cout << ans << endl;
  }
}