パズルゲーム（tomoenage）を解くプログラム

tomoenage というゲームを作りました。
以下はそのステージ作成を補助するためのプログラムです。

#include <stdio.h>
#include <stdlib.h>

/*
   tomoenage ゲームの解法解析プログラム
   解法の数と手順の最短、最長を表示します
   コード中のコメント解除で手順も表示します
*/

#define W 16
#define H 16

#define START_Y 15  // スタート位置 Ｙ座標
#define START_X 0   // スタート位置 Ｘ座標

int d[H][W] ={
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,3,3,4,3,3,3,3,3,3,3,3,3,3,3,3},
  {3,4,3,2,3,3,3,3,3,3,3,3,3,3,3,3},
  {0,2,0,0,3,3,3,3,3,3,3,3,3,3,3,3},
  {0,0,2,2,3,3,3,3,3,3,3,3,3,3,3,3},
  {0,0,2,2,4,3,3,3,3,3,3,3,3,3,3,3}
};

int flag = 0;  // 解けないなら 0 解けるなら 1

int count = 0;

int index = 0;

int hy[100];
int hx[100];

int s = 0;

int *px = NULL;
int *py = NULL;

int *pm = NULL;

int mx = 0;
int mn = 2000000000;

void move(int y, int x, int d2[H][W]){
  if(d[y][x] == 1 || d[y][x] == 2 || d[y][x] == 3 || d2[y][x] == 1){
    return;
  }
  
  d2[y][x] = 1;
  
  if(y - 1 >= 0)move(y - 1, x, d2);
  if(x + 1 < W)move(y, x + 1, d2);
  if(y + 1 < H)move(y + 1, x, d2);
  if(x - 1 >= 0)move(y, x - 1, d2);
}

void f(int y, int x, int *m, int c1){
  int d2[H][W];
  
  int *m2 = (int *)malloc(s * sizeof(int));
  
  for(int j = 0; j < H; j++){
    for(int i = 0; i < W; i++){
      d2[j][i] = 0;
    }
  }
  
  move(y, x, d2);
  
  for(int i = 0; i < s; i++){
    m2[i] = m[i];
    
    if(d2[py[i]][px[i]] == 1){
      m2[i] = 1;
    }
  }
  
  int c = 0;
  
  for(int i = 0; i < s; i++){
    if(m2[i] == 1){
      c++;
    }
  }
  
  if(c == s){
    // 解法の手順を表示する場合はコメントをはずす
    //for(int i = 0; i < index; i++){
    //  printf("%d:%d\n", hy[i], hx[i]);
    //}
    //getchar();
    if(c1 > mx)mx = c1;
    if(c1 < mn)mn = c1;
    printf("#");
    flag = 1;
    count++;
  }
  
  for(int j = 0; j < H; j++){
    for(int i = 0; i < W; i++){
      if(d2[j][i] == 1){
        int dy[4] = {-1, 0, 1,  0};
        int dx[4] = { 0, 1, 0, -1};
        
        for(int r = 0; r < 4; r++){
          int ay = dy[r];
          int ax = dx[r];
          int by = dy[(r + 2) % 4];
          int bx = dx[(r + 2) % 4];
          
          if(j + ay < 0 || j + ay >= H)continue;
          if(i + ax < 0 || i + ax >= W)continue;
          if(j + by < 0 || j + by >= H)continue;
          if(i + bx < 0 || i + bx >= W)continue;
          
          if(d[j + ay][i + ax] == 2 && d[j + by][i + bx] == 0){
            hy[index] = j;
            hx[index] = i;
            index++;
            d[j + ay][i + ax] = 0;
            d[j + by][i + bx] = 3;
            f(j, i, m2, c1 + 1);
            index--;
            d[j + ay][i + ax] = 2;
            d[j + by][i + bx] = 0;
          }
          if(d[j + ay][i + ax] == 1 && d[j + by][i + bx] == 0){
            d[j + ay][i + ax] = 0;
            d[j + by][i + bx] = 2;
            f(j, i, m2, c1 + 1);
            d[j + ay][i + ax] = 1;
            d[j + by][i + bx] = 0;
          }
        }
      }
    }
  }
  
  free(m2);
}

int main(){
  int x = START_X;
  int y = START_Y;
  
  for(int j = 0; j < H; j++){
    for(int i = 0; i < W; i++){
      if(d[j][i] == 4){
        s++;
      }
    }
  }
  
  py = (int *)malloc(s * sizeof(int));
  px = (int *)malloc(s * sizeof(int));
  
  pm = (int *)malloc(s * sizeof(int));
  
  int index = 0;
  
  for(int j = 0; j < H; j++){
    for(int i = 0; i < W; i++){
      if(d[j][i] == 4){
        py[index] = j;
        px[index] = i;
        index++;
      }
    }
  }
  
  for(int i = 0; i < s; i++){
    pm[i] = 0;
  }
  
  f(y, x, pm, 0);
  
  if(flag == 1){
    printf("YES:%d\n", count);
  }
  else{
    printf("NO:%d\n", count);
  }
  
  printf("max:%d min:%d\n", mx, mn);
  
  free(pm);
  free(px);
  free(py);
  
  return 0;
}