[algogeeks] SPOJ STRDIST

[ganesha]

http://www.spoj.pl/problems/STRDIST/

Getting WA repeatedly. Can someone help me with the below code.


#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
        int k,l;
        scanf("%d %d",&k,&l);

        string str1 = "";
        string str2 = "";

        if (k>0)
                cin >> str1;
        if(l>0)
                cin >> str2;

        str1 = "0" + str1;
        str2 = "0" + str2;

        int m,n;

        m = k;
        n = l;

        int pos[][3] = {
                {2,1,0},
                {0,2,1},
                {1,0,2}
        };

        int I,I1,I2;
        int posIdx = 0;


        int dp[3][n+1];

        for (int i = 0 ; i < 3; i++)
                for (int j = 0 ; j <=n; j++)
                        dp[i][j] = 200;

        dp[0][0] = 0;

        for (int i = 0 ; i <= m; i++)
        {
                if (i >= 2)
                {
                        I = pos[posIdx][0];     I1 = pos[posIdx][1]; I2 = 
pos[posIdx][2];
                }
                else
                {
                        I=i;I1=i-1;
                }

                for (int j = 0 ; j <=n; j++)
                {
                        if (i == 0 && j == 0) continue;

                        if ( j - i > 105)
                                break;

                        bool updated = false;

                        if (j > 0)
                        {
                                dp[I][j] = min(dp[I][j],dp[I][j-1] + 1);
                                updated = true;
                        }
                        if (i > 0)
                        {
                                if (updated)
                                        dp[I][j] = min(dp[I][j],dp[I1][j] + 1);
                                else
                                        dp[I][j] = dp[I1][j] + 1;
                        }
                        if (i > 0 && j > 0 && str1[i] == str2[j])
                        {
                                dp[I][j] = min(dp[I][j],dp[I1][j-1]);
                        }
                        if (str1[i] == str2[j-1] && str1[i-1] == str2[j] && 
i>=2 && j>=2)
                        {
                                dp[I][j] = min(dp[I][j],dp[I2][j-2] + 1);
                        }
                        if (i > 0 && j > 0 && str1[i] != str2[j])
                        {
                                dp[I][j] = min(dp[I][j],dp[I1][j-1] + 1);
                        }
                }
                if (i >= 2)
                {
                        posIdx = (posIdx + 1)%3;
                }
        }

        printf("%d\n",dp[k%3][l]);

        return 0;
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.