I successfully solved a very simple and yet conceptual problem on SPOJ called ( ABCPATH ) using three concepts(multi source BFS, Dijkstra and DP) and in the process I hit a surprising result in between, while implementing DP solution.

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.

I submitted two times for the problem. One wrong answer and second accepted. The only thing I did differently in the accepted logic was taking maximum after travelling into all eight directions. To give more insight let me add the logic of code.

Link to the Accepted solution : Accepted Solution

Link to the Wrong solution : Wrong Solution with one line shifted

The main logic of code that got SUBMITTED is ( 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]); // THE LINE DIFFERENT FROM THE WRONG SUBMISSION
                }
     
   }

and the code that got WRONG, is :

       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]); // THE LINE DIFFERENT FROM THE WRONG SUBMISSION
                        }
                    }
                }
        }

So, I ran both the code on multiple test cases trying to debug where the conflict comes and the code fails. Also, getting maximum over individual distances at the time of computation and maximum once the value is computed over all eight directions, how should the value be different?

I would be really obliged to see a test case to get the core logic of code failure in one case and pass in another.

Thanks