I successfully solved a very simple and yet conceptual problem on SPOJ called ( ABCPATH ) but hit a intriguing doubt in between.

Let me first describe the problem in a nutshell :

We are given a 2D array of characters from 'A' to 'Z'. We need to start from 'A' and find the longest path with consecutive alphabets ( cannot trace back like 'N' to 'M' and then again a 'N'). Direction of travel is horizontal, vertical and diagonal.

While submitting I got WA for the the Dynamic Programming logic I wrote which got accepted by changing position of just one line!

The code that got submitted ( Omitting the code for taking input and headers) :

` for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { dp[i][j] = -INF; cin >> arr[i][j];

if (arr[i][j] == 'A')
                dp[i][j] = 1;
        }
    }

    for (char ch = 'A'; ch <= 'Z'; ch++)
    {
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
            {
                if (arr[i][j] != ch)
                    continue;

                for (int k = 0; k < 8; k++)
                {
                    ll newX = i + rows[k];
                    ll newY = j + cols[k];
                    if (isValid(newX, newY) and (arr[newX][newY] == (ch - 1)))
                    {
                        dp[i][j] = max(dp[newX][newY] + 1, dp[i][j]);
                    }
                }

                **longest = max(longest, dp[i][j]);**
            }
    }

`

and the code that got WRONG, where the highlighted line was just placed inside the logic of travelling in all eight directions :

` for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { dp[i][j] = 0; cin >> arr[i][j];

if (arr[i][j] == 'A')
                dp[i][j] = 1;
        }

    for (char ch = 'A'; ch <= 'Z'; ch++)
    {
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
            {
                if (arr[i][j] != ch)
                    continue;

                for (int k = 0; k < 8; k++)
                {
                    ll newX = i + rows[k];
                    ll newY = j + cols[k];
                    if (isValid(newX, newY) and (arr[newX][newY] == (ch - 1)))
                    {
                        dp[i][j] = max(dp[newX][newY] + 1, dp[i][j]);
                        **longest = max(longest, dp[i][j]);**
                    }
                }
            }
    }

`