📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1922| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

N皇后这样的DFS题怎么在找到第一个解的时候就不再继续?

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
突然想到这个问题。。
比如leetcode 51题的N皇后,会遍历所有的解的可能性然后打印出所有的解,方法是用for循环里面加上dfs:
    private void dfsHelper(int n, int[] col, int row) {
        if (row == n) {
            //...
            //加到解集里面去
            return;
        }
        for (int i = 0; i < n; i++) {
            col[row] = i;
            if (checkValid(row, col)) {
                dfsHelper(n, col, row + 1);
            }
        }
    }

那如果想在找到第一个皇后之后就不再继续下去,该怎么修改呢?

上一篇:leetcode题量增大如何刷完?
下一篇:湾区跳槽
🔗
cjlsysu 2017-4-17 17:34:09 | 只看该作者
全局:
加个标志变量就行了
回复

使用道具 举报

🔗
Xing2017 2017-4-23 07:36:50 | 只看该作者
全局:
在递归程序外面建立一个全局变量flag = 0,如果找到答案就设置flag为1, 然后每次递归前检查flag的值,如果为1直接return。 楼主试试看能不能解决。
回复

使用道具 举报

🔗
354886 2017-4-23 07:46:22 | 只看该作者
全局:
给dfs一个返回值。如果子问题返回了true就直接返回不再继续回溯。
回复

使用道具 举报

🔗
cstdlib 2017-4-23 08:44:23 | 只看该作者
全局:
  1. private bool dfsHelper(int n, int[] col, int row) {
  2.         bool found = false;
  3.         if (row == n) {
  4.             //...
  5.             //加到解集里面去
  6.             return true;
  7.         }
  8.         for (int i = 0; i < n && !found; i++) {
  9.             col[row] = i;
  10.             if (checkValid(row, col)) {
  11.                 found = found || dfsHelper(n, col, row + 1);
  12.             }
  13.         }
  14.         return found;
  15.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表