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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
