DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

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) 시간이 든다.