125. Shtirlits. Немножко о графах и переборе.

Полный текст задачи доступен здесь.

После прочтения задачи и ограничений на количество ячеек равное максимум 9 в голову приходит переборное решение, но тут возникает вопрос какой именно должен быть перебор. Если пробовать перебирать все возможные значения A [i, j] то очевидно, что число порядка pow(10,9) во временные ограничения не уложится.

Попробуем перебирать не сами числа в позиции [i][j], а выбирать те соседние ячейки в которых числа могут оказаться больше чем в текущей, по условию задачи максимальное число в этом случае может быть 4 для каждой ячейки(Для угловых - 2, для центральной [1][1] - 4, а для всех остальных 3). Очевидно что перебор в данном случае не должен занять много времени.
На выходе перебора имеем для каждой ячейки конкретные ячейки значения в которых больше чем в текущей.
Примерно это выглядит вот так в первом приближении:

1. void solve(int pos,int lastMove)
2. {
3.   if (pos == n * n)
4.   {
5.     if (BuildSolution())
6.     {
7.       output();
8.       exit(0);
9.     }
10.   }
11.   else
12.   {
13.     int x = pos / n;
14.     int y = pos % n;
15.     int steps = mas[x][y];
16.     if (steps)
17.     {
18.       for(int i = lastMove + 1;i < 4; i++)
19.       {
20.         int nextX = x + movx[i];
21.         int nextY = y + movy[i];
22.         int vertFrom = pos, vertTo = GetVert(nextX, nextY);
23.         if (isValid(nextX, nextY) && !adj[vertTo][vertFrom])
24.         {
25.           mas[x][y]--;
26.           adj[vertTo][vertFrom] = 1;
27.           solve(pos,i);
28.           adj[vertTo][vertFrom] = 0;
29.           mas[x][y] ++;
30.         }
31.       }
32.     }
33.     else solve(pos+1,-1);
34.   }
35. }

* This source code was highlighted with Source Code Highlighter.

Процедура solve принимает два аргумента первый из которых указывает на текущее положение перебираемого элемента, замечу что pos <= n*n, а для вычисления положения элемента в матрице используются конструкции в строках 13 и 14, а второй аргумент это последний тип движения который был использован(movx, movy - стандартные массивы движений, для перемещения строго по горизонтали или вертикали).
Далее имеем в матрице adj дугу между вершинами i и j, только в том случае если значение в матрице A[i/n][i%n] > A[j/n][j%n], где n - размерность поля, а А матрица расстановки войск.
Между некоторыми ячейками, находящимися в зоне доступной для перемещения нет дуг, а значит значения в исходной матрице А для этих элементов равны. Т.е. иными словами далее нам необходимо сконденсировать граф объединяя в группу вершины доступные при перемещении, но не имеющие дуг:

void DfsGroupSeparation(int vert, int group)
{
  used[vert] = 1;
  groups[vert] = group;
  for(int i=0;i<n*n;i++)
    if (ByStep(vert,i) && !used[i] && !adj[vert][i] && !adj[i][vert])
      DfsGroupSeparation(i, group);
}

for(int i=0;i<n*n;i++)
    if (!used[i])
      DfsGroupSeparation(i,i);

* This source code was highlighted with Source Code Highlighter.

Задача почти решена, остаётся лишь на полученном графе построить топологический порядок и аккуратно вывести ответ. Фрагмент построения порядка:

1. void DfsTopologicalSort(int group)
2. {
3.   used[group] = 1;
4.   for(int i=0;i<n*n;i++)
5.   {
6.     if (groups[i] == group) // find all verticies from the same group
7.     {
8.       for(int j=0;j<n*n;j++)
9.       {
10.         if (adj[i][j])
11.         {
12.           if (!used[groups[j]])
13.             DfsTopologicalSort(groups[j]);
14.           else
15.             if (used[groups[j]] == 1)
16.             {
17.               isCycle = true;
18.               break;
19.             }
20.         }
21.       }
22.     }
23.   }
24.   used[group] = 2;
25.   order.push_back(group);
26. }
27.  
28. for(int i=0;i<n*n;i++) // for all vertices
29.   {
30.     if (!used[groups[i]])
31.     {
32.       DfsTopologicalSort(groups[i]);
33.       if (isCycle)
34.         return false;
35.     }
36.   }

* This source code was highlighted with Source Code Highlighter.

И в заключении не забыть выводить NO SOLUTION как это приведено в условии задачи.