In function memo, I send two ints r and c. Then I check if there is any enemy on row r, after and including column c, and on column c after and including row r.If there is, res[r][c] = min( res[r + 1][c] , min[r][c + 1] ) + 1, else

res[r][c] = res[r + 1][c + 1].

My idea is, if I shoot on row r, then all I have to think about is the rectangle (r+1,c) to (row,col), because row r contains no more enemies.

My code:

Code: Select all

```
#include<iostream>
using namespace std ;
#define MAX 1005
int row ;
int col ;
bool board[MAX][MAX] ;
int res[MAX][MAX] ;
int move[MAX][MAX] ;
int memo(int r , int c)
{
if(r == row + 1 || c == col + 1)
return 0 ;
if(res[r][c] != -1)
return res[r][c] ;
bool enemy = false ;
for(int i = c ; i <= col ; i++)
{
if(board[r][i] == true)
{
enemy = true ;
break ;
}
}
for(int i = r ; i <= row ; i++)
{
if(board[i][c] == true)
{
enemy = true ;
break ;
}
}
if(!enemy)
{
res[r][c] = memo(r + 1 , c + 1) ;
move[r][c] = 2 ;
return res[r][c] ;
}
if(memo(r , c + 1) < memo(r + 1 , c))
move[r][c] = 1 ;
else
move[r][c] = 3 ;
res[r][c] = min(memo(r , c + 1) , memo(r + 1 , c)) + 1 ;
return res[r][c] ;
}
void show(int r , int c)
{
if(r == row + 1 || c == col + 1)
return ;
if(move[r][c] == 2)
show(r + 1 , c + 1) ;
else if(move[r][c] == 1)
{
printf(" c%d" , c) ;
show(r , c + 1) ;
}
else
{
printf(" r%d" , r) ;
show(r + 1 , c) ;
}
}
int main()
{
int n ;
freopen("1.txt" , "r" , stdin) ;
while(scanf("%d %d %d" , &row , &col , &n) && row && col && n)
{
memset(board , false , sizeof(board)) ;
memset(res , -1 , sizeof(res)) ;
for(int i = 0 ; i < n ; i++)
{
int r , c ;
scanf("%d %d" , &r , &c) ;
board[r][c] = true ;
}
printf("%d" , memo(1 , 1)) ;
show(1 , 1) ;
printf("\n") ;
}
}
```