平成30年度応用情報技術者試験午後問題3

h30h_ap_pm3_1.c

#include <stdio.h>

#define M 4
#define N 3

int m, n, printFlag;

int board[M+1][N+1] = { 0 };
int dv[] = { 0, -2, -1,  1,  2,  2,  1, -1, -2};
int dh[] = { 0,  1,  2,  2,  1, -1, -2, -2, -1};

void search(int i, int v, int h);
void printBoard(void);

void search(int i, int v, int h)
{
  if (v >= 1 && v <= m) {
    if (h >= 1 && h <= n) {
      if (board[v][h] == 0) {   /* 通過したマスを判定する。 */
        board[v][h] = i;        /* 移動順序を記録する。 */
        if (i == M * N) {
          printBoard();         /* 解答を印字する。 */
          printFlag = 1;
        }
        else {
          for (int j = 1; j <= 8; j++) {
            search(i+1, v+dv[j], h+dh[j]); /* 次の移動先を調べる。 */
          }
        }
        board[v][h] = 0;        /* 移動順序を取り消す。 */
      }
    }
  }
}

void printBoard()
{
  for (int v = 1; v <= m; v++) {
    for (int h = 1; h <= n; h++) {
      printf("%3d", board[v][h]);
    }
    printf("\n");
  }
  printf("\n");
}

int main(void)
{
  m = M;
  n = N;
  printFlag = 0;
  search(1, 1, 1);
  if (!printFlag) {
    printf("解答がありません。\n");
  }
  return 0;
}

http://maehrm.hatenablog.com/entry/2018/05/04/101933