SPOJ TOURIST - Tourist

Problem Statement:
SPOJ - TOURIST

Solution:
Seems like a lot of work, seems like a some graph problem, seems like something convoluted... But once you've found the enlightenment, this is a pretty nice DP problem.

Firstly, realize that we can rephrase the problem as finding two paths from top-left corner (0,0) to the bottom-right corner (H-1, W-1) that maximizes the number of '*' covered. Then, realize that the length of the path is constant, H+W-2, no matter how we move.



Now consider extending the two paths simultaneously. Let D(k, i, j) be the maximum number of '*' covered by paths starting from (0,0) to (k-i, i) and (k-j, j). Each time we move, we increase k by one, and for each i, j, we can choose to increase their value. Hence each step we have 4 different possibilities. Hence, D(k,i,j) is the max { D(k-1, i-1, j), D(k-1, i, j-1), D(k-1, i-1, j-1), and D(k-1, i, j)} + {0, 1, or 2 depending on whether (k-i,i) and (k-j,j) covers '*'). If any of (k-i,i) or (k-j,j) are '#', we can set D(k,i,j) = \(-\infty\).

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

int dp[203][101][101];
int H, W;
string board[103];

int main(){
    int TC;
    scanf("%d", &TC);
    while(TC--){
        scanf("%d%d",&W, &H);
        for(int i=0;i<H;++i){
            cin >> board[i];
        }
        dp[0][0][0] = (board[0][0] == '*' ? 1 : 0);
        for(int k=1;k<=H+W-2;++k){
            for(int i=0;i<=W-1;++i){
                for(int j=0;j<=W-1;++j){
                    dp[k][i][j] = -123456;
                    if (i>k || j>k || k-i >= H || k-j >= H) continue;
                    if(board[k-i][i] == '#' || board[k-j][j] == '#'){
                        continue;
                    }
                    if(k-1-i >= 0 && k-1-j >= 0) {
                        dp[k][i][j] = dp[k-1][i][j];
                    }
                    if(i > 0 && k-1-j >= 0) {
                        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j]);
                    }
                    if(j > 0 && k-1-i >= 0) {
                        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]);
                    }
                    if(i > 0 && j > 0) {
                        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i-1][j-1]);
                    }
                    if(i==j){
                        if(board[k-i][i] == '*') dp[k][i][j]++;
                    } else {
                        if(board[k-i][i] == '*') dp[k][i][j]++;
                        if(board[k-j][j] == '*') dp[k][i][j]++;
                    }
                }
            }
        }
        printf("%d\n", dp[H+W-2][W-1][W-1]);
    }
    return 0;
}