Пятнашки

При решении задачи удобно использовать двумерный целочисленный массив a[1..n][1..n], который первоначально следует заполнить числами согласно описанному формату исходного состояния. Здесь можно воспользоваться тем фактом, что a[y][x]=(y-1)*n+x, кроме последнего элемента a[n][n], который соответствует пустому месту и должен быть равен нулю.

Далее, следует организовать моделирование, где мы будем перемещать пустое место (нолик в матрице) согласно последовательности заданных действий. Данная последовательность может быть считана в некоторую строку s и в дальнейшем обработана в цикле, где некоторый символ s[k] будет представлять направление движения нолика на k-м шаге. Координаты пустого места мы можем всегда хранить в переменных (x,y) и на каждом шаге их менять, параллельно проводя смену ячеек a[y][x] и a[yy][xx], где (x’,y’) – координата, в которую должен переместиться нолик. Если на каком-то шаге (x’,y’) окажется за пределами доски, то следует вывести текст ошибки с номером k и завершить программу. Если подобной ошибки в процессе моделирования не возникнет, то по завершении всех действий мы в нашем массиве получим ответ на задачу.

Алгоритмическая реализация:

  read(n,s)

  for y=1..n
    for x=1..n 
      a[y][x]=y*n+x+1
  a[n][n]=0

  x=y=n
  for k=1..len(s){
    x’=x; y’=y
    if(s[k]='U') y’--
    if(s[k]='D') y’++
    if(s[k]='L') x’--
    if(s[k]='R') x’++
    if(x’*y’*(x’-n-1)*(y’-n-1)==){
      write(’ERROR ’,k)
      exit
    }
    a[y][x] <---> a[y’][x’]
    y=y’; x=x’
  }

  for y=1..n{
    for x=1..n 
      write(a[y][x], ’ ’)
    writeln
  }

[Обсуждение] [Все попытки] [Задача]