Skip to content

Instantly share code, notes, and snippets.

@Abreto
Created October 19, 2013 15:52
Show Gist options
  • Save Abreto/7057719 to your computer and use it in GitHub Desktop.
Save Abreto/7057719 to your computer and use it in GitHub Desktop.
Wikioi 1010
/* Wikioi - Problem 1010 Dabing crossing the river. */
#include <stdio.h>
#define CONTROLEDBYHORSE(i, j) ( (X == (i) && Y == (j)) || (X-1 == (i) && Y-2 == (j)) || (X-2 == (i) && Y-1 == (j)) || (X-2 == (i) && Y+1 == (j)) || (X-1 == (i) && Y+2 == (j)) || (X+1 == (i) && Y-2 == (j)) || (X+2 == (i) && Y-1 == (j)) || (X+2 == (i) && Y+1 == (j)) || (X+1 == (i) && Y+2 == (j)) )
#define OUTOFBOARD(i, j) ( ((i) > n) || ((j) > m) )
typedef long long int lint;
int n = 0, m = 0;
int X = 0, Y = 0;
lint dp_v[21][21] = {{0}};
lint dp(int i, int j)
{
lint *ans = &(dp_v[i][j]);
if( *ans )
return *ans;
if( OUTOFBOARD(i,j) || CONTROLEDBYHORSE(i,j) )
return 0;
if( n == i && m == j )
return 1;
return ( *ans = dp(i+1,j) + dp(i,j+1) );
}
int
main(void)
{
scanf("%d %d %d %d", &n, &m, &X, &Y);
printf("%lld\n", dp(0,0));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment