返回信息流题目大概就是
n*n个格子的棋盘上，每个格子写1，或者空，要求删除一些1，使得棋盘上每行每列最多只有一个1。
给出一个棋盘，求最多剩下多少个1。
感觉有点像旁边谷歌的题？.？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #98725同步于 2019/12/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】算法渣渣请教个问题 棋盘
FromMars
2019/12/16镜像同步18 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
感觉用八皇后的方法可以做。关键看n有多大
【 在 FromMars (T_):) 的大作中提到: 】
: 题目大概就是
: n*n个格子的棋盘上，每个格子写1，或者空，要求删除一些1，使得棋盘上每行每列最多只有一个1。
: 给出一个棋盘，求最多剩下多少个1。
: ...................
比如5*5的棋牌，然后有9个棋子，(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(3,1),(4,1),(5,1).answer=?
【 在 laplace 的大作中提到: 】
: 答案是 min(row, col)，其中 row 是多少行有棋子，col是多少列有棋子
我也觉得是八皇后，dfs + 回溯
同时还可以用map记录中间状态，因为后面的状态很大概率会重复计算
hash key可以用bit位表示，取决于n多大
【 在 shisuan 的大作中提到: 】
: 感觉用八皇后的方法可以做。关键看n有多大
:
八皇后做法肯定是能做的，只是复杂度太高了。
如果想复杂度优秀一点，还得用二分图最大匹配的模型来做。复杂度能做到最坏O(n^(5/2))
【 在 xxpxxxxp (xxpxxxxp) 的大作中提到: 】
: 我也觉得是八皇后，dfs + 回溯
: 同时还可以用map记录中间状态，因为后面的状态很大概率会重复计算
: hash key可以用bit位表示，取决于n多大