AdvancedProgrammingNBU/f80789_5b.cpp at master · rralev/AdvancedProgrammingNBU · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>

using namespace std;

const int MOVE_X[] = {-2, -1, 1, 2,  2,  1, -1, -2};
const int MOVE_Y[] = { 1,  2, 2, 1, -1, -2, -2, -1};
const int INF = 1 << 10;

int table[12][12];
int n, x, y;
bool solution_found;

bool check(int x, int y)
{
  return x > 0 && x <= n && y > 0 && y <= n && table[x][y] == 0;
}

int count_conflicts(int x, int y)
{
  int cnt = 0;

  for (int i = 0; i < 8; i++)
  {
    int next_x = x + MOVE_X[i];
    int next_y = y + MOVE_Y[i];

    if (check(next_x, next_y)) cnt++;
  }

  return cnt;
}

void dfs(int x, int y, int d)
{
  if (solution_found == true) return;

  table[x][y] = d;
  if (n * n == d)
  {
    solution_found = true;
    for (int i = 1; i <= n; i++)
    {
      printf("%d", table[i][1]);
      for (int j = 2; j <= n; j++)
      {
        printf(" %d", table[i][j]);
      }
      printf("\n");
    }

    return;
  }

  int best = 10;
  int best_x = INF, best_y = INF;

  for (int i = 0; i < 8; i++)
  {
    int next_x = x + MOVE_X[i];
    int next_y = y + MOVE_Y[i];

    if (check(next_x, next_y))
    {
      int cnt = count_conflicts(next_x, next_y);
      if (best > cnt)
      {
        best = cnt;
        best_x = next_x;
        best_y = next_y;
      }
    }
  }

  if (best < INF) dfs(best_x, best_y, d + 1);

  table[x][y] = 0;
}

int main()
{
  while (scanf("%d%d%d", &n, &x, &y) != EOF)
  {
    for (int i = 1; i <= 10; i++)
      for (int j = 1; j <= 10; j++)
        table[i][j] = 0;

    solution_found = false;
    dfs(x, y, 1);
  }

  return 0;
}