Problem: https://www.spoj.com/problems/ABCPATH/
Could someone please point me to the mistake in my solution? It gets WA on some test. The idea is DFS from every ‘A’ with memoization.
const int mxR = 55, mxC = 55;
int R, C;
char grid[mxR][mxC];
int memo[mxR][mxC];
bool inside_grid(int row, int col) {
return 0 <= row && row < R && 0 <= col && col < C;
}
int dfs(int row, int col, char prev) {
if(!inside_grid(row, col) || grid[row][col] != prev+1)
return -1;
if(memo[row][col] != -1) {
return memo[row][col];
}
int ans = 0;
for(int dx : {-1, 0, +1}) {
for(int dy : {-1, 0, +1}) {
ans = max(ans, dfs(row+dx,col+dy,grid[row][col]));
}
}
return memo[row][col] = ans + 1;
}
int solve() {
memset(memo, -1, sizeof memo);
vector<ii> starts;
for(int row = 0; row < R; ++row) {
for(int col = 0; col < C; ++col) {
scanf("%c", &grid[row][col]);
if(grid[row][col] == 'A')
starts.emplace_back(row, col);
}
scanf("%*c");
}
int ans = 0;
for(auto rc : starts) {
ans = max(ans, dfs(rc.first, rc.second, 'A'-1));
}
return ans;
}