DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Building a Binary Grid

問題に戻る

解説

N≥5N \geq 5N≥5에서는 기본적으로 각 행을 0, 1, 0, 1, …\ldots…로 채운다. 같은 문자가 이어지면 오른쪽으로, 문자가 바뀌면 위나 아래로 한 칸 이동하면 문자열을 만들 수 있다. 첫 번째 열은 값을 반대로 두어 완전히 번갈아 나오는 두 문자열을 모두 세로 경로로 처리한다.

첫 번째 열을 뒤집으면 전부 같은 문자인 문자열을 가로로 만들 수 없으므로 (2,N)(2,N)(2,N)을 0, (3,N)(3,N)(3,N)을 1로 바꾼다. 이 두 칸을 이용하면 00...0과 11...1도 만들 수 있다. 문자가 한 번만 바뀌는 경우에는 4, 5번째 행을 사용하고, 두 번 이상 바뀌는 경우에는 마지막 열에 닿지 않게 시작 행을 고르면 수정한 두 칸을 피할 수 있다.

N≤4N \leq 4N≤4에서는 칸이 최대 161616개뿐이므로 모든 격자를 확인하고 깊이 우선 탐색으로 필요한 경로를 찾는다. 전체 출력 경로 생성에는 O(NQ)O(NQ)O(NQ) 시간이 든다.