{"problem":{"name":"J. Теория больших шахмат","description":{"content":"Шелдон и Леонард в очередной раз решили написать программу для игры в 3D-шахматы. Пока они сконцентрировали внимание на реализации стратегии самой игры. Но чтобы не терять время, они бросили клич к на","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10096J"},"statements":[{"statement_type":"Markdown","content":"Шелдон и Леонард в очередной раз решили написать программу для игры в 3D-шахматы. Пока они сконцентрировали внимание на реализации стратегии самой игры. Но чтобы не терять время, они бросили клич к научной общественности — помочь реализовать простейшие подпрограммы, на которые им, естественно, жаль тратить свое драгоценное время.\n\nОдна из задач — определить путь, посредством которого конь может попасть из одной клетки в другую за наименьшее число ходов, всё время оставаясь на одном и том же уровне (каждый уровень является плоской квадратной шахматной доской). В пределах одного уровня конь перемещается по стандартным шахматным правилам, но некоторые клетки доски перемещают оказавшиеся на них фигуры на другие уровни, поэтому коню запрещено оказываться в таких клетках в конце хода. \n\nПервая строка содержит целое число N (3 ≤ N ≤ 1000) — размер шахматной доски.\n\nСледующие N строк описывают шахматную доску. i-я из них содержит N символов, j-й из которых равен '.', если клетка (i; j) является обычной клеткой доски, '*', если клетка является началом или концом искомого пути, либо '+', если в клетку запрещено попадать коню.\n\nГарантируется, что ввод содержит ровно два символа '*'.\n\nВ первой строке выведите число M — количество клеток, входящих в искомый путь, включая начальные и конечные клетки.\n\nДалее выведите M строк, каждая из которых содержит пару целых чисел — вертикальную и горизонтальную координаты клеток, которые посещает конь; строки должны быть упорядочены в порядке обхода. Строки доски нумеруются сверху вниз, начиная с 0. Столбцы доски нумеруются слева направо, начиная с 0.\n\nЕсли искомого пути не существует, выведите единственное число 0.\n\nШахматный конь может перемещаться на две клетки вверх, влево, вниз или вправо, а затем на одну клетку в любом перпендикулярном направлении. Конь «перепрыгивает» через клетки, то есть непосредственно посещает только начальную и конечную клетки хода.\n\n## Входные Данные\n\nПервая строка содержит целое число N (3 ≤ N ≤ 1000) — размер шахматной доски.Следующие N строк описывают шахматную доску. i-я из них содержит N символов, j-й из которых равен '.', если клетка (i; j) является обычной клеткой доски, '*', если клетка является началом или концом искомого пути, либо '+', если в клетку запрещено попадать коню.Гарантируется, что ввод содержит ровно два символа '*'.\n\n## Выходные Данные\n\nВ первой строке выведите число M — количество клеток, входящих в искомый путь, включая начальные и конечные клетки.Далее выведите M строк, каждая из которых содержит пару целых чисел — вертикальную и горизонтальную координаты клеток, которые посещает конь; строки должны быть упорядочены в порядке обхода. Строки доски нумеруются сверху вниз, начиная с 0. Столбцы доски нумеруются слева направо, начиная с 0.Если искомого пути не существует, выведите единственное число 0.\n\n## Примеры\n\nВходные данные5......**.................Выходные данные41 12 30 41 2Входные данные5*..*...++................Выходные данные60 02 14 03 22 40 3Входные данные5*......+...+............*Выходные данные0\n\n## Примечание\n\nШахматный конь может перемещаться на две клетки вверх, влево, вниз или вправо, а затем на одну клетку в любом перпендикулярном направлении. Конь «перепрыгивает» через клетки, то есть непосредственно посещает только начальную и конечную клетки хода.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the size of the square chessboard ($3 \\leq N \\leq 1000$).  \nLet $ B \\in \\{., *, +\\}^{N \\times N} $ be the board, where:  \n- $ B[i][j] = '.' $: normal cell,  \n- $ B[i][j] = '*' $: start or end cell (exactly two such cells),  \n- $ B[i][j] = '+' $: forbidden cell (constrained to avoid at the end of any move).  \n\nLet $ s = (r_s, c_s) $ and $ t = (r_t, c_t) $ be the coordinates of the two `*` cells (start and target).  \n\nLet $ \\mathcal{M} = \\{ (\\pm 2, \\pm 1), (\\pm 1, \\pm 2) \\} $ be the set of 8 valid knight moves.  \n\n**Constraints**  \n1. The knight may only move to cells $ (i', j') $ such that:  \n   - $ (i', j') \\in [0, N-1] \\times [0, N-1] $,  \n   - $ B[i'][j'] \\neq '+' $,  \n   - $ (i', j') - (i, j) \\in \\mathcal{M} $.  \n2. The knight must not land on a `+` cell at the end of any move.  \n3. The path must start at $ s $ and end at $ t $.  \n\n**Objective**  \nFind the shortest path (minimum number of moves) from $ s $ to $ t $, visiting a sequence of valid cells.  \nOutput:  \n- If a path exists:  \n  - $ M $: number of cells in the path (including start and end),  \n  - $ M $ lines: coordinates $ (r, c) $ of each visited cell in order.  \n- If no path exists: output `0`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10096J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}