## Thursday, December 18, 2014

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