{"id":633,"date":"2026-07-12T21:19:19","date_gmt":"2026-07-12T13:19:19","guid":{"rendered":"https:\/\/mitongxue.cn\/?p=633"},"modified":"2026-07-12T21:19:19","modified_gmt":"2026-07-12T13:19:19","slug":"%e8%bf%b7%e5%ae%ab%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"https:\/\/mitongxue.cn\/index.php\/2026\/07\/12\/%e8%bf%b7%e5%ae%ab%e9%97%ae%e9%a2%98\/","title":{"rendered":"\u8ff7\u5bab\u95ee\u9898"},"content":{"rendered":"\n

\u63cf\u8ff0<\/h2>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u6709\u4e00\u4e2a h<\/mi><\/mrow><\/semantics><\/math>h<\/em> \u884c w<\/mi><\/mrow><\/semantics><\/math>w<\/em> \u5217\u7684\u7f51\u683c\uff0c\u6211\u4eec\u4f7f\u7528 (<\/mo>i<\/mi>,<\/mo>j<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(i<\/em>,j<\/em>) \u8868\u793a\u7f51\u683c\u4e2d\u4ece\u4e0a\u5f80\u4e0b\u6570\u7b2c i<\/mi><\/mrow><\/semantics><\/math>i<\/em> \u884c\u548c\u4ece\u5de6\u5f80\u53f3\u6570\u7b2c j<\/mi><\/mrow><\/semantics><\/math>j<\/em> \u5217\u7684\u5355\u5143\u683c\u3002\u6bcf\u4e2a\u65b9\u683c\u8981\u4e48\u662f\u53ef\u4ee5\u901a\u8fc7\u7684\u7a7a\u65b9\u683c \u20180\u2019<\/mtext><\/mrow><\/semantics><\/math>\u20180\u2019 \uff0c\u8981\u4e48\u662f\u4e0d\u53ef\u901a\u8fc7\u7684\u5899\u65b9\u683c \u20181\u2019<\/mtext><\/mrow><\/semantics><\/math>\u20181\u2019 \uff0c\u7279\u522b\u7684\uff0c\u7f51\u683c\u7684\u56db\u5468\u90fd\u662f\u5899\u65b9\u683c\uff0c\u4f60\u53ef\u4ee5\u6cbf\u7740\u7a7a\u65b9\u683c\u4e0a\u4e0b\u5de6\u53f3\u968f\u610f\u79fb\u52a8\uff1a\u4ece (<\/mo>x<\/mi>,<\/mo>y<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>,y<\/em>) \u5411\u4e0a\u79fb\u52a8\u4e00\u683c\u5373\u62b5\u8fbe (<\/mo>x<\/mi>\u2212<\/mo>1<\/mn>,<\/mo>y<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>\u22121,y<\/em>) \u3001\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u5373\u62b5\u8fbe (<\/mo>x<\/mi>+<\/mo>1<\/mn>,<\/mo>y<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>+1,y<\/em>) \u3001\u5411\u5de6\u79fb\u52a8\u4e00\u683c\u5373\u62b5\u8fbe (<\/mo>x<\/mi>,<\/mo>y<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>,y<\/em>\u22121) \u3001\u5411\u53f3\u79fb\u52a8\u4e00\u683c\u5373\u62b5\u8fbe (<\/mo>x<\/mi>,<\/mo>y<\/mi>+<\/mo>1<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>,y<\/em>+1) \u3002<\/p>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u73b0\u5728\uff0c\u4f60\u4f4d\u4e8e\u8ff7\u5bab\u7684\u5165\u53e3 (<\/mo>0<\/mn>,<\/mo>0<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(0,0) \uff0c\u60f3\u8981\u524d\u5f80\u7ec8\u70b9 (<\/mo>h<\/mi>\u2212<\/mo>1<\/mn>,<\/mo>w<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(h<\/em>\u22121,w<\/em>\u22121) \u3002\u8bf7\u8f93\u51fa\u4e00\u6761\u4ece\u8d77\u70b9\u5230\u7ec8\u70b9\u7684\u53ef\u884c\u8def\u5f84\u3002<\/p>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u4fdd\u8bc1\u8d77\u70b9\u548c\u7ec8\u70b9\u4e00\u5b9a\u4e3a\u7a7a\u65b9\u683c\uff0c\u4f60\u59cb\u7ec8\u53ef\u4ee5\u627e\u5230\u4e14\u80fd\u552f\u4e00\u627e\u5230\u4e00\u6761\u4ece\u8d77\u70b9\u51fa\u53d1\u5230\u8fbe\u7ec8\u70b9\u7684\u53ef\u884c\u8def\u5f84\u3002<\/p>\n\n\n\n

\u8f93\u5165\u63cf\u8ff0\uff1a<\/h3>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u7b2c\u4e00\u884c\u8f93\u5165\u4e24\u4e2a\u6574\u6570 h<\/mi>,<\/mo>w<\/mi>(<\/mo>1<\/mn>\u2266<\/mo>h<\/mi>,<\/mo>w<\/mi>\u2266<\/mo>100<\/mn>)<\/mo><\/mrow><\/mrow><\/semantics><\/math>h<\/em>,w<\/em>(1\u2266h<\/em>,w<\/em>\u2266100) \u4ee3\u8868\u8ff7\u5bab\u7684\u884c\u6570\u548c\u5217\u6570\u3002
<\/mspace><\/mrow><\/semantics><\/math>\u6b64\u540e h<\/mi><\/mrow><\/semantics><\/math>h<\/em> \u884c\uff0c\u7b2c i<\/mi><\/mrow><\/semantics><\/math>i<\/em> \u884c\u8f93\u5165 w<\/mi><\/mrow><\/semantics><\/math>w<\/em> \u4e2a\u6574\u6570 a<\/mi>i<\/mi>,<\/mo>1<\/mn><\/mrow><\/msub>,<\/mo>a<\/mi>i<\/mi>,<\/mo>2<\/mn><\/mrow><\/msub>,<\/mo>\u2026<\/mo>,<\/mo>a<\/mi>i<\/mi>,<\/mo>w<\/mi><\/mrow><\/msub>(<\/mo>0<\/mn>\u2266<\/mo>a<\/mi>i<\/mi>,<\/mo>j<\/mi><\/mrow><\/msub>\u2266<\/mo>1<\/mn>)<\/mo><\/mrow><\/mrow><\/semantics><\/math>a<\/em>i<\/em>,1\u200b,a<\/em>i<\/em>,2\u200b,\u2026,a<\/em>i<\/em>,w<\/em>\u200b(0\u2266a<\/em>i<\/em>,j<\/em>\u200b\u22661) \u4ee3\u8868\u8ff7\u5bab\u7684\u5e03\u5c40\u3002\u5176\u4e2d\uff0ca<\/mi>i<\/mi>,<\/mo>j<\/mi><\/mrow><\/msub>=<\/mo>0<\/mn><\/mrow><\/semantics><\/math>a<\/em>i<\/em>,j<\/em>\u200b=0 \u8868\u793a\u5355\u5143\u683c (<\/mo>i<\/mi>,<\/mo>j<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(i<\/em>,j<\/em>) \u662f\u7a7a\u65b9\u683c\uff0ca<\/mi>i<\/mi>,<\/mo>j<\/mi><\/mrow><\/msub>=<\/mo>1<\/mn><\/mrow><\/semantics><\/math>a<\/em>i<\/em>,j<\/em>\u200b=1 \u8868\u793a\u5355\u5143\u683c (<\/mo>i<\/mi>,<\/mo>j<\/mi>)<\/mo><\/mrow><\/semantics><\/math>(i<\/em>,j<\/em>) \u662f\u5899\u65b9\u683c\u3002<\/p>\n\n\n\n

\u8f93\u51fa\u63cf\u8ff0\uff1a<\/h3>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u8f93\u51fa\u82e5\u5e72\u884c\uff0c\u7b2c i<\/mi><\/mrow><\/semantics><\/math>i<\/em> \u884c\u8f93\u51fa\u4e24\u4e2a\u6574\u6570 x<\/mi>i<\/mi><\/msub>,<\/mo>y<\/mi>i<\/mi><\/msub><\/mrow><\/semantics><\/math>x<\/em>i<\/em>\u200b,y<\/em>i<\/em>\u200b \uff0c\u8868\u793a\u8def\u5f84\u7684\u7b2c i<\/mi><\/mrow><\/semantics><\/math>i<\/em> \u6b65\u62b5\u8fbe\u7684\u5355\u5143\u683c\u5750\u6807\u4e3a (<\/mo>x<\/mi>i<\/mi><\/msub>,<\/mo>y<\/mi>i<\/mi><\/msub>)<\/mo><\/mrow><\/semantics><\/math>(x<\/em>i<\/em>\u200b,y<\/em>i<\/em>\u200b) \u3002<\/p>\n\n\n\n

<\/mspace><\/mrow><\/semantics><\/math>\u4f60\u9700\u8981\u4fdd\u8bc1\u8f93\u51fa\u7684\u8def\u5f84\u662f\u7b26\u5408\u9898\u76ee\u8981\u6c42\u7684\uff0c\u5373\u4ece\u8d77\u70b9 (<\/mo>0<\/mn>,<\/mo>0<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(0,0) \u51fa\u53d1\uff0c\u5230\u8fbe\u7ec8\u70b9 (<\/mo>h<\/mi>\u2212<\/mo>1<\/mn>,<\/mo>w<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow><\/semantics><\/math>(h<\/em>\u22121,w<\/em>\u22121) \uff0c\u4e14\u8def\u5f84\u4e0a\u6bcf\u4e2a\u5355\u5143\u683c\u90fd\u662f\u7a7a\u65b9\u683c\uff0c\u884c\u8d70\u7684\u5355\u5143\u683c\u90fd\u662f\u5f7c\u6b64\u76f8\u90bb\u7684\u3002<\/p>\n\n\n\n

\u793a\u4f8b1<\/h2>\n\n\n\n

\u8f93\u5165\uff1a<\/p>\n\n\n\n

5 5\n0 1 0 0 0\n0 1 1 1 0\n0 0 0 0 0\n0 1 1 1 0\n0 0 0 1 0\n<\/code><\/pre>\n\n\n\n
\u590d\u5236<\/p>\n\n\n\n
\u8f93\u51fa\uff1a<\/p>\n\n\n\n
(0,0)\n(1,0)\n(2,0)\n(2,1)\n(2,2)\n(2,3)\n(2,4)\n(3,4)\n(4,4)\n<\/code><\/pre>\n\n\n\n
\u590d\u5236<\/p>\n\n\n\n
\u793a\u4f8b2<\/h2>\n\n\n\n
\u8f93\u5165\uff1a<\/p>\n\n\n\n
5 5\n0 1 0 0 0\n0 1 0 1 0\n0 0 0 0 1\n0 1 1 1 0\n0 0 0 0 0<\/code><\/pre>\n\n\n\n
\u590d\u5236<\/p>\n\n\n\n
\u8f93\u51fa\uff1a<\/p>\n\n\n\n
(0,0)\n(1,0)\n(2,0)\n(3,0)\n(4,0)\n(4,1)\n(4,2)\n(4,3)\n(4,4)<\/code><\/pre>\n\n\n\n
\u601d\u8def\uff1a<\/h2>\n\n\n\n
    \n
  1. \u8bfb\u5165\u6570\u7ec4\uff0c\u4e8c\u7ef4<\/li>\n\n\n\n
  2. \u91c7\u7528BFS\u5165\u961f\u51fa\u961f\u65b9\u5f0f\uff0c\u901a\u8fc7\u5224\u65ad\u662f\u5426\u8d70\u5230\u5e95\uff0c\u662f\u5426\u6709\u672a\u51fa\u961f<\/li>\n\n\n\n
  3. \u56db\u4e2a\u65b9\u5411\u5904\u7406<\/li>\n\n\n\n
  4. \u9700\u8981\u8bb0\u5f55\u4e0a\u4e00\u6b65\u53ca\u5f53\u524d\u5750\u6807\u662f\u5426\u8d70\u8fc7<\/li>\n\n\n\n
  5. \u56de\u6eaf\u65b9\u5f0f<\/li>\n<\/ol>\n\n\n\n
    void (async function () {\n    \/\/ Write your code here\n    const [h, w] = (await readline()).split(\" \").map(Number);\n    const grid = [];\n    for (let i = 0; i < h; i++) {\n        grid[i] = (await readline()).split(\" \");\n    }\n\n    \/\/console.log(grid)\n    const dirs = [\n        [-1, 0],\n        [1, 0],\n        [0, 1],\n        [0, -1],\n    ];\n    const queue = [];\n    const res = [];\n    const pre = Array.from({ length: h }, () => Array(w).fill(null));\n    const visited = Array.from({ length: h }, () => Array(w).fill(false));\n    let isEnd = false;\n    visited[0][0] = true;\n    queue.push([0, 0]);\n    \/\/console.log(grid);\n    while (queue.length && !isEnd) {\n        const [x, y] = queue.shift();\n        if (x === h - 1 && y === w - 1) {\n            isEnd = true;\n            \/\/console.log(\"\u7ed3\u675f\", x, y);\n            break;\n        }\n        for (const [dx, dy] of dirs) {\n            const tempX = x + dx;\n            const tempY = y + dy;\n            if (\n                tempX >= 0 &&\n                tempX < h &&\n                tempY >= 0 &&\n                tempY < w &&\n                grid[tempX][tempY] === \"0\" &&\n                !visited[tempX][tempY]\n            ) {\n                \/\/console.log([tempX, tempY]);\n                queue.push([tempX, tempY]);\n                visited[tempX][tempY] = true;\n                pre[tempX][tempY] = [x, y];\n            }\n        }\n    }\n    console.log(pre, \"pre\");\n\n    let path = [];\n    let cur = [h - 1, w - 1];\n    while (cur) {\n        path.unshift(cur);\n        cur = pre[cur[0]][cur[1]];\n    }\n    console.log(path);\n    for (const [i, j] of path) {\n        console.log(`(${i},${j})`);\n    }\n})();<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u63cf\u8ff0 \u6709\u4e00\u4e2a hh \u884c&nbs..<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,11,51],"tags":[],"class_list":["post-633","post","type-post","status-publish","format-standard","hentry","category-js","category-front","category-51"],"featured_image_urls":{"full":"","thumbnail":"","medium":"","medium_large":"","large":"","1536x1536":"","2048x2048":""},"author_info":{"info":["\u9648 \u67d0\u4eba"]},"category_info":"JS<\/a> \u524d\u7aef<\/a> \u725b\u5ba2<\/a>","tag_info":"\u725b\u5ba2","comment_count":"0","_links":{"self":[{"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/posts\/633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/comments?post=633"}],"version-history":[{"count":1,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/posts\/633\/revisions"}],"predecessor-version":[{"id":634,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/posts\/633\/revisions\/634"}],"wp:attachment":[{"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/media?parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/categories?post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mitongxue.cn\/index.php\/wp-json\/wp\/v2\/tags?post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}