{"id":1275,"date":"2020-01-08T10:56:18","date_gmt":"2020-01-08T02:56:18","guid":{"rendered":"https:\/\/wyxxt.org.cn\/?p=1275"},"modified":"2023-12-04T15:51:18","modified_gmt":"2023-12-04T07:51:18","slug":"%e5%b2%9b%e5%b1%bf%e9%97%ae%e9%a2%98-%e6%b7%b1%e5%ba%a6%e9%81%8d%e5%8e%86%ef%bc%88dfs-depth-first-search%ef%bc%89","status":"publish","type":"post","link":"https:\/\/wyxxt.org.cn\/?p=1275","title":{"rendered":"\u5c9b\u5c7f\u95ee\u9898\u2014\u2014\u6df1\u5ea6\u4f18\u5148\u904d\u5386\uff08DFS Depth First Search\uff09"},"content":{"rendered":"

\u7406\u8bba\u57fa\u7840<\/h3>\n

\n BFS\u548cDFS\u662f\u4e24\u79cd\u5341\u5206\u91cd\u8981\u7684\u641c\u7d22\u7b97\u6cd5\uff0cBFS\u9002\u5408\u67e5\u627e\u6700\u4f18\u89e3\uff0cDFS\u9002\u5408\u67e5\u627e\u662f\u5426\u5b58\u5728\u89e3(\u6216\u8005\u8bf4\u80fd\u627e\u5230\u4efb\u610f\u4e00\u4e2a\u53ef\u884c\u89e3)\u3002\u7528\u8fd9\u4e24\u79cd\u7b97\u6cd5\u5373\u53ef\u4ee5\u89e3\u51b3\u5927\u90e8\u5206\u6811\u548c\u56fe\u7684\u95ee\u9898\u3002**
\n \u5e7f\u5ea6\u904d\u5386\u904d\u5229\u7528\u961f\u5217\u5904\u7406
\n \u6df1\u5ea6\u904d\u5386\u4f7f\u7528\u9012\u5f52\u7b97\u6cd5\u5904\u7406\n<\/p><\/blockquote>\n

\u4ee3\u7801\u793a\u4f8b<\/h3>\n

\n 1\u662f\u9646\u5730 0\u662f\u6c34
\n \u9646\u5730\u901a\u8fc7\u6c34\u5e73\u4e0e\u5782\u76f4\u65b9\u5411\u8fde\u63a5
\n \u9ed8\u8ba4\u7f51\u683c\u56db\u5468\u4e3a\u6c34
\n \u6c42\u5c9b\u5c7f\u7684\u6570\u91cf<\/p>\n

5 5
\n 1 1 1 1 0
\n 1 1 0 0 1
\n 0 0 1 0 1
\n 0 1 1 0 0
\n 1 0 0 1 1\n<\/p><\/blockquote>\n

package main\nimport (\n    \"fmt\"\n    \"os\"\n)\n\n\/\/\u8bfb\u53d6\u7f51\u683c\nfunc readGrid(filename string) [][]int {\n    file, err := os.Open(filename)\n    if err != nil {\n        panic(err)\n    }\n    var row, col int\n    fmt.Fscanf(file, \"%d %d\",&row,&col)\n    dfs := make([][]int,row)\n    for i := range dfs {\n        dfs[i] = make([]int,col)\n        for j :=  range dfs[i] {\n            fmt.Fscanf(file, \"%d\", &dfs[i][j])\n        }\n    }\n    return dfs\n}\n\n\/\/\u83b7\u53d6\u5c9b\u5c7f\u6570\u91cf\nfunc numIslands(grid [][]int) int {\n    if grid == nil || len(grid) == 0 {\n        return 0\n    }\n    num := 0\n    for i := range gird {\n        for j := range gird[i] {\n            if grid[i][j] == 1 {\n                num++\n                dfs(grid, i, j)\n            }\n        }\n    }\n    return num\n}\n\n\/\/\u6df1\u5ea6\u904d\u5386\nfunc dfs(grid [][]int, i, j int) {\n    row := len(gird)\n    col := len(gird[0])\n    if i < 0 || i>row || j<0 || j>col || gird[i][j] == 0 {\n        return\n    }\n    gird[i][j] = '0'\n    dfs(gird,i,j-1)\n    dfs(grid,i-1,j)\n    dfs(grid,i,j+1)\n    dfs(grid,i+1,j)\n}\n\nfunc main() {\n    grid := readGrid(\"dfs\/dfs.in\")\n    num := numIslands(grid)\n    fmt.Println(num)\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u7406\u8bba\u57fa\u7840 BFS\u548cDFS\u662f\u4e24\u79cd\u5341\u5206\u91cd\u8981\u7684\u641c\u7d22\u7b97\u6cd5\uff0cBFS\u9002\u5408\u67e5\u627e\u6700\u4f18\u89e3\uff0cDFS\u9002\u5408\u67e5\u627e\u662f\u5426\u5b58\u5728\u89e3(\u6216\u8005\u8bf4\u80fd\u627e\u5230 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[15],"tags":[400],"class_list":["post-1275","post","type-post","status-publish","format-standard","hentry","category-15","tag-400"],"_links":{"self":[{"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/posts\/1275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1275"}],"version-history":[{"count":10,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/posts\/1275\/revisions"}],"predecessor-version":[{"id":2003,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=\/wp\/v2\/posts\/1275\/revisions\/2003"}],"wp:attachment":[{"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wyxxt.org.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}