Cod sursa(job #275768)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 10 martie 2009 17:33:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#define lg_max 1050

int v,m,n;
char voci[lg_max][lg_max],sol[lg_max];
int cost[lg_max][lg_max];
int mata[lg_max][lg_max];

void citire()
{
	freopen ("note.in","r",stdin);
	freopen ("note.out","w",stdout);
	scanf("%d %d",&v,&n);
	for(int i=1;i<=v;i++)
		for(int j=1;j<=n;j++)
          {
               scanf("%d",&voci[i][j]);
               mata[j][voci[i][j]]=1;
          }

	scanf("%d",&m);
	for(int i=1;i<=m;i++)
          scanf("%d",&sol[i]);
}

int corect(int nr,int nota)
{
          if (mata[nr][nota]==1)
               return 1;
	return 0;
}

void solve()
{
	cost[0][0]=0;
	for(int i=1;i<=n;i++)
          cost[i][0]=i;

	for(int j=1;j<=m;j++)
          cost[0][j]=j;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			{
				cost[i][j]=lg_max;
				if (cost[i][j]>cost[i-1][j]+1)
                         cost[i][j]=cost[i-1][j]+1;
				if (cost[i][j]>cost[i][j-1]+1)
                         cost[i][j]=cost[i][j-1]+1;
				if (cost[i][j]>cost[i-1][j-1]+1)
                         cost[i][j]=cost[i-1][j-1]+1;
				if (corect(i,sol[j]))
					if (cost[i][j]>cost[i-1][j-1])
                              cost[i][j]=cost[i-1][j-1];
			}
}


int main()
{
	citire();
	solve();
	printf("%d",cost[n][m]);
	return 0;
}