Tiles

TPA

2018/08/27

Categories: algorithms

Solve script

tiles.c

#include <stdio.h>

#define M 5000
#define N 5000
#define BIGPRIME 1000000007

#define exists(a,b) ((0<=(a))&&((a)<M)&&(0<=(b))&&((b)<N))

int main() {
  static int park[M][N], ways[M][N];
  int i, j;
  FILE *tf = fopen("tiles.txt", "r");
  for (i = 0; i < M; ++i)
    for (j = 0; j < N; ++j)
      fscanf(tf, "%d", &park[i][j]);
  puts("Done scanning tiles.txt...");
  ways[M-1][0] = 1;
  for (i = 0; i < M + N; ++i) {
    for (j = 0; j < N; ++j) {
      if (exists(M-1-(i-j), j)) {
	if (!park[M-1-(i-j)][j]) {
	  if (exists(M-1-(i-j),j-1))
	    ways[M-1-(i-j)][j] += ways[M-1-(i-j)][j-1] % BIGPRIME;
	  if (exists(M-(i-j),j))
	    ways[M-1-(i-j)][j] += ways[M-(i-j)][j] % BIGPRIME;
	  ways[M-1-(i-j)][j] %= BIGPRIME;
	}
      }
    }
  }
  printf("Answer: %d\n", ways[0][N-1]);
  return 0;
}