{"id":127684,"date":"2020-06-16T20:17:58","date_gmt":"2020-06-16T12:17:58","guid":{"rendered":"http:\/\/4563.org\/?p=127684"},"modified":"2020-06-16T20:17:58","modified_gmt":"2020-06-16T12:17:58","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-%e6%b9%96%e9%9d%a2%e9%80%83%e8%b7%91","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=127684","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] \u6e56\u9762\u9003\u8dd1"},"content":{"rendered":"
\n
\n
\n

[leetcode\/lintcode \u9898\u89e3] \u6e56\u9762\u9003\u8dd1 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hakunamatata11 <\/span> <\/i> 6<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

Albert \u88ab\u56f0\u5728\u7ed3\u51b0\u7684\u6e56\u9762\u4e0a\u3002 \u4ed6\u60f3\u77e5\u9053\u4ed6\u662f\u5426\u80fd\u56de\u5230\u5cb8\u4e0a\u3002 \u4ed6\u76ee\u524d\u5728\u96ea\u5806\u4e0a\uff0c\u8fd9\u7ed9\u4e86\u4ed6\u4e00\u4e9b\u6469\u64e6\u529b\u3002\u4f46\u4e00\u65e6\u4ed6\u8e0f\u8fdb\u51b0\u9762\uff0c\u4ed6\u4f1a\u671d\u540c\u4e00\u65b9\u5411\u6ed1\u884c\uff0c\u76f4\u5230\u649e\u4e0a\u53e6\u4e00\u4e2a\u96ea\u5806\u3002 \u51b0\u9762\u4e0a\u4e5f\u6709\u4ed6\u5fc5\u987b\u907f\u5f00\u7684\u5371\u9669\u7684\u6d1e\u3002<\/p>\n

Albert \u7684\u5c0f\u72d7\uff0cKuna\uff0c\u4e5f\u88ab\u56f0\u5728\u4e00\u4e2a\u4e0d\u540c\u7684\u96ea\u5806\u4e0a\u3002Albert \u80fd\u627e\u5230\u4ed6\u7684\u5c0f\u72d7\u5e76\u628a\u5b83\u5e26\u5230\u5cb8\u4e0a\u5417\uff1f<\/p>\n

Albert \u53ea\u80fd\u6c34\u5e73\u548c\u5782\u76f4\u79fb\u52a8\u3002 \u4ed6\u6700\u7ec8\u9700\u8981\u6765\u5230\u5cb8\u8fb9\uff0c\u79bb\u5f00\u6e56\u9762 \u8f93\u5165\u5305\u62ec\u4ee5\u4e0b\u53c2\u6570\uff1a<\/p>\n

    \n
  • side_length: \u6e56\u9762\u7684\u957f\u5ea6\uff08\u8fd9\u662f\u4e00\u4e2a\u6b63\u65b9\u5f62\uff09<\/li>\n
  • lake_grid: \u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u4ee3\u8868\u6e56\u9762\uff0c\u5176\u4e2d 0 \u4ee3\u8868\u51b0\u9762\uff0c1 \u4ee3\u8868\u96ea\u5806\uff0c-1 \u4ee3\u8868\u6d1e<\/li>\n
  • albert_row: Albert \u6240\u5728\u7684\u96ea\u5806\u7684\u884c<\/li>\n
  • albert_column: Albert \u6240\u5728\u7684\u96ea\u5806\u7684\u5217<\/li>\n
  • kuna_row: Kuna \u6240\u5728\u7684\u96ea\u5806\u7684\u884c<\/li>\n
  • kuna_column: Kuna \u6240\u5728\u7684\u96ea\u5806\u7684\u5217<\/li>\n<\/ul>\n

    \u5728\u7ebf\u8bc4\u6d4b\u5730\u5740: https:\/\/www.lintcode.com\/problem\/lake-escape\/?utm_source=sc-v2ex-fks<\/p>\n

    \u6837\u4f8b<\/p>\n

    \u8f93\u5165: 7 [[0,0,0,0,0,0,0],[0,0,-1,0,0,0,0],[0,0,1,-1,0,-1,0],[-1,0,1,0,0,0,0],[0,1,1,0,0,1,0],[-1,0,-1,0,-1,0,0],[0,0,0,0,0,0,0]] 4 1 3 2 \u8f93\u51fa: true <\/code><\/pre>\n
    \u8bf4\u660e\uff1a<\/p>\n
    \u5982\u56fe\u6240\u793a\u3002\u9ec4\u8272\u683c\u5b50\u662f Albert \u7684\u4f4d\u7f6e\uff0c\u7ea2\u8272\u683c\u5b50\u662f Kuna \u7684\u4f4d\u7f6e\u3002Albert \u53ef\u4ee5\u5411\u53f3\u8d70\u5230(4,2)\uff0c\u5411\u4e0a\u8d70\u5230(3,2)\uff0c\u7136\u540e\u5411\u53f3\u8d70\uff0c\u79bb\u5f00\u6e56\u9762\u3002<\/p>\n
    \"[leetcode\/lintcode<\/p>\n
    [\u9898\u89e3] \u76f4\u63a5 bfs \u53bb\u641c\u7d22\u5373\u53ef<\/p>\n
    public class Solution {     \/**      * @param side_length: the length of a side of the lake (it's a square)      * @param lake_grid: a 2D matrix representing the lake 0= ice, 1= snowbank, -1= hole       * @param albert_row: row of Albert's snowbank      * @param albert_column: column of Albert's snowbank       * @param kuna_row: row of Kuna's snowbank       * @param kuna_column: column of Kuna's snowbank      * @return: a bool - whether Albert can escape      *\/     public boolean lakeEscape(int side_length, int[][] lake_grid, int albert_row, int albert_column, int kuna_row, int kuna_column) {         \/\/ write your code here         int dx[] = {0, 1, 0, -1};         int dy[] = {1, 0, -1, 0};         int [][][] visit = new int[2][side_length][side_length];         Queue<Integer> qx = new LinkedList<>();         Queue<Integer> qy = new LinkedList<>();         Queue<Integer> qc = new LinkedList<>();         qc.offer(0); qx.offer(albert_row); qy.offer(albert_column);         while (!qx.isEmpty()){             int cc = qc.poll();              int cx = qx.poll();             int cy = qy.poll();             if (visit[cc][cx][cy] != 0) continue;             visit[cc][cx][cy] = 1;             for (int i = 0; i < 4; i++){                 int nowx = cx, nowy = cy;                 boolean flag1 = true, flag2 = false, flag3 = false;                 for (int j = 0; j <= side_length; j++){                     nowx += dx[i]; nowy += dy[i];                     if (nowx == kuna_row && nowy == kuna_column) flag3 = true;                     if (nowx < 0 || nowx >= side_length || nowy < 0 || nowy >= side_length)                     {                         flag2 = true; break;                     }                     if (lake_grid[nowx][nowy] == -1)                     {                         flag1 = false; break;                     }                     if (lake_grid[nowx][nowy] == 1) break;                 }                 if (flag2){                     if (cc == 1 || flag3) return true;                 }                 else if (flag1){                     if (flag3){                         qc.offer(1);                         qx.offer(nowx);                         qy.offer(nowy);                     }                     else{                         qc.offer(cc);                         qx.offer(nowx);                         qy.offer(nowy);                     }                 }             }         }         return false;     } } <\/code><\/pre>\n
    \u66f4\u591a\u8bed\u8a00\u4ee3\u7801\u53c2\u89c1\uff1a https:\/\/www.jiuzhang.com\/solution\/lake-escape\/?utm_source=sc-v2ex-fks<\/p>\n<\/p><\/div>\n
     \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
     <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
      \n
    • \n","protected":false},"excerpt":{"rendered":"
      [leetcode\/lintcod…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/127684"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=127684"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/127684\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=127684"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=127684"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=127684"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}