Cod sursa(job #254481)

Utilizator ScrazyRobert Szasz Scrazy Data 7 februarie 2009 12:22:43
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.74 kb
#include <cstdio>
#include <cstring>

#define nmax 51
#define kmax 500

const int dx[] = {-1, 1,  0, 0};
const int dy[] = { 0, 0, -1, 1};

int n, m, K;
int a[nmax][nmax];
int x1, y1, x2, y2;
int dp[nmax][nmax][kmax];

inline int min(int a, int b)
{
	return a < b ? a : b;
}

void read()
{
	scanf("%d%d%d", &n, &m, &K);
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	--x1; --y1; --x2; --y2;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] % K != 0) a[i][j] %= K;
			else if (a[i][j] != 0) a[i][j] = K;
		}
}

int jo(int x, int y)
{
	return x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 0;
}

int solve(int i, int j, int k, int pi, int pj)
{	
	if (dp[i][j][k] != -1) return dp[i][j][k];
	
	if (i == x1 && j == y1)
	{
		if ((k * a[i][j])%K == 0) return 0;
		else return -1;
	}

	for (int l = 0; l < 4; ++l)
		if (jo(i + dx[l], j + dy[l]))
		{
			if (pi == i + dx[l] && pj == j + dy[l]) continue;
			if ((k * a[i][j]) % K == 0 && dp[i][j][k] == -1) dp[i][j][k] = solve(i + dx[l], j + dy[l], K, i, j) + 1;
			else if (dp[i][j][k] == -1) dp[i][j][k] = solve(i + dx[l], j + dy[l], (k * a[i][j]) % K, i, j) + 1;
			else if ((k * a[i][j]) % K == 0) 
			{
				int t = solve(i + dx[l], j + dy[l], K, i, j) + 1;
				if (t != 0 && dp[i][j][k] > t) dp[i][j][k] = t;
			}
			else
			{
				int t = solve(i + dx[l], j + dy[l], (k * a[i][j]) % K, i, j) + 1;
				if (t != 0 && dp[i][j][k] > t) dp[i][j][k] = t;
			}

			if (dp[i][j][k] == 0) dp[i][j][k] = -1;
		}

	return dp[i][j][k];
}

int main()
{
	freopen("kdrum.in","r",stdin);
	freopen("kdrum.out","w",stdout);
	read();
	
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(x2, y2, 1, -1, -1) + 1);

	return 0;
}