# CFR 374 C. Inna and Dima ( DP )

Problem - C - Codeforces

1. 先選一個 'D' 的格子，在滿足條件而可以移動的前提下進行：
2. 移動到上下左右的其中一格 'I'
3. 移動到上下左右的其中一格 'M'
4. 移動到上下左右的其中一格 'A'
5. 移動到上下左右的其中一格 'D'
6. 從 2. 重新進行

TL: 1000 ms
ML: 256 MB

dp[ i ][ j ]：以 ( i, j ) 開始最多可以走多少 "DIMA"。( 不限 G[ i ][ j ] 是否為 'D' )

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;
}
}
```