<
查看: 1413|回复: 4
收起左侧

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

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎

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

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

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 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (303)
 
 
4% (13)    👎
加个标志变量就行了
回复

使用道具 举报

Xing2017 2017-4-23 07:36:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
在递归程序外面建立一个全局变量flag = 0,如果找到答案就设置flag为1, 然后每次递归前检查flag的值,如果为1直接return。 楼主试试看能不能解决。
回复

使用道具 举报

354886 2017-4-23 07:46:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   77% (72)
 
 
22% (21)    👎
给dfs一个返回值。如果子问题返回了true就直接返回不再继续回溯。
回复

使用道具 举报

cstdlib 2017-4-23 08:44:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (5)
 
 
0% (0)    👎
  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.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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