blog。很强的思维题。
如果能用 \(0\sim 2^T-1\) 表示出来(\(T\le k\))那么显然也可以用 \(0\sim 2^k-1\) 表示出来,转化为求最小的合法填数方案 \(T\)。
如图所示,红色是唯一路径,黄粉色处是一个拐角。让在黄粉色拐弯的路径不合法,可以给两者填 \(2^0\) 与 \(2^1\),然后这个值一直往左下延申,把这一整段屏蔽掉。
类似地,每出现一个单独的拐角,\(T\) 就该加一。右上部分的拐弯是同理的,可以不考虑。做完了。
code,时间复杂度 \(O(T(n+m))\)。