{"id":3410,"date":"2022-10-26T10:19:00","date_gmt":"2022-10-26T02:19:00","guid":{"rendered":"https:\/\/codingbar.ai\/content\/?p=3410"},"modified":"2022-11-03T16:36:27","modified_gmt":"2022-11-03T08:36:27","slug":"apcs-2022%e5%b9%b410%e6%9c%88-%e8%a7%a3%e9%a1%8c%e6%80%9d%e7%b7%92python%e5%8f%83%e8%80%83%e4%bd%9c%e6%b3%95","status":"publish","type":"post","link":"https:\/\/codingbar.ai\/content\/apcs-2022%e5%b9%b410%e6%9c%88-%e8%a7%a3%e9%a1%8c%e6%80%9d%e7%b7%92python%e5%8f%83%e8%80%83%e4%bd%9c%e6%b3%95\/","title":{"rendered":"APCS 2022\u5e7410\u6708 \u89e3\u984c\u601d\u7dd2+Python\u53c3\u8003\u4f5c\u6cd5"},"content":{"rendered":"\n

\u5beb\u5b8cAPCS\u984c\u76ee\u5f8c\u7684\u788e\u788e\u5ff5<\/h2>\n\n\n\n

\u672c\u6b21\u984c\u76ee\u57fa\u672c\u4e0a\u4f86\u8aaa\u7b97\u662f\u6bd4\u8f03\u55ae\u7d14\u7684
\u7b2c\u4e00\u984c\u662f\u70ba\u8fed\u4ee3\u7684\u57fa\u672c\u984c\uff0c\u4ee5\u53ca\u5982\u4f55\u5728\u591a\u500b\u6578\u5b57\u4e2d\u627e\u51fa\u6700\u5927\u6700\u5c0f\u503c\u3002
\u7b2c\u4e8c\u984c\u662f\u6a21\u64ec\u984c\uff0c\u8003\u9a57\u5c0d\u65bc\u4e0d\u540c\u60c5\u5883\u4e0b\u7684\u8655\u7406\u65b9\u5f0f\u8207\u908f\u8f2f\uff0c\u518d\u8f14\u4ee5\u9663\u5217\u9032\u884c\u8a18\u9304\u8b80\u53d6\uff0c\u6bd4\u8d77\u9ad8\u96e3\u5ea6\u7684\u6f14\u7b97\u6cd5\u66f4\u50cf\u662f\u5728\u8003\u9a57\u7d30\u4e0d\u7d30\u5fc3\u3002
\u7b2c\u4e09\u984c\u8003\u9a57\u8655\u7406\u6a39\u7684\u80fd\u529b\uff0c\u7d50\u5408\u905e\u8ff4\u53ef\u4ee5\u5feb\u901f\u89e3\u6c7a\u3002
\u7b2c\u56db\u984c\u53ef\u4ee5\u4f7f\u7528\u4e8c\u641c+BFS\u9032\u884c\u8655\u7406\uff0c\u4f46\u7531\u65bcPython\u7684\u9650\u5236\u6015TLE\uff0c\u6240\u4ee5\u662f\u4f7f\u7528Dijkstra+BFS\u9032\u884c\u8655\u7406<\/p>\n\n\n\n

ZeroJudge \u984c\u76ee<\/h2>\n\n\n\n
  1. \u5df4\u58eb\u7ad9\u724c<\/a><\/li>
  2. \u904b\u8ca8\u7ad9<\/a><\/li>
  3. \u77f3\u7a9f\u63a2\u96aa<\/a><\/li>
  4. \u84cb\u6b65\u9053<\/a><\/li><\/ol>\n\n\n\n

    \u5df4\u58eb\u7ad9\u724c<\/strong><\/h2>\n\n\n\n

    Youtube\u8b1b\u89e3\u5f71\u7247<\/a><\/p>\n\n\n\n

    \u984c\u76ee\u7c21\u8ff0\uff1a
    \u9996\u5148\u6703\u8f38\u5165\u4e00\u500b\u6578\u5b57 n \uff0c\u6b64 n \u4ee3\u8868\u4e86\u7ad9\u724c\u6578\u91cf\uff0c\u63a5\u4e0b\u4f86\u6703\u6709 n \u884c\uff0c\u6bcf\u884c2\u500b\u6574\u6578\u4ee3\u8868\u4e86\u7ad9\u724c\u5ea7\u6a19\uff0c\u82e5\u6709\u4e00\u4eba\u6703\u4f9d\u5e8f\u7d93\u904e\u9019\u500bn\u500b\u7ad9\u9ede\uff0c\u8acb\u8a08\u7b97\u76f8\u9130\u5169\u7ad9\u7684\u66fc\u54c8\u9813\u8ddd\u96e2(\u516c\u5f0f\uff1a| x1<\/sub> – x2<\/sub> | + | y1<\/sub> – y2<\/sub> | )\u3002<\/p>\n\n\n\n

    \u6700\u5f8c\u8f38\u51fa \u6700\u5927<\/span><\/strong> \u7684\u66fc\u54c8\u9813\u8ddd\u96e2\u4ee5\u53ca \u6700\u5c0f<\/span><\/strong> \u7684\u66fc\u54c8\u9813\u8ddd\u96e2\uff0c\u4e2d\u9593\u9700\u4ee5\u7a7a\u683c\u505a\u70ba\u9593\u683c\u3002<\/p>\n\n\n\n

    \"APCS\"<\/figure>\n\n\n\n

    \u5047\u8a2d n \u8f38\u51655\uff0c\u5206\u5225\u70ba
    2 8
    2 1 -> |2-2| + |1-8| = 7
    3 4 -> |3-2| + |4-1| = 4
    5 8 -> |5-3| + |8-4| = 6
    7 4 -> |7-5| + |4-8| = 6
    \u6709\u4ee5\u4e0a\u53ef\u4ee5\u5f97\u77e5\uff1a\u6700\u5927\u503c\u70ba7\uff0c\u6700\u5c0f\u503c\u70ba4<\/p>\n\n\n\n

    \u6709\u4e86\u4ee5\u4e0a\u6982\u5ff5\u5f8c\u4f86\u601d\u8003\u4e00\u4e0b\u7c21\u55ae\u7684\u89e3\u984c\u6b65\u9a5f
    1. \u8f38\u5165\uff1a\u4e00\u500b n \uff0c\u63a5\u4e0b\u4f86\u5229\u7528for i in range(n) \u4f86\u63a5 n \u500b\u5169\u500b\u6578\u5b57
    2. \u8a08\u7b97\u908f\u8f2f\uff1a\u5fc5\u9808\u5148\u6709\u7b2c\u4e00\u5c0d\u6578\u5b57\uff0c\u63a5\u4e0b\u4f86\u6bcf\u4e00\u5c0d\u6578\u5b57\u7686\u8ddf\u4e0a\u8863\u5c0d\u6578\u5b57\u9032\u884c\u66fc\u54c8\u9813\u8ddd\u96e2\u7684\u904b\u7b97
    3. \u8f38\u51fa\uff1a\u6703\u9700\u8981\u6700\u5927\u503c\u8207\u6700\u5c0f\u503c -> \u5728\u958b\u59cb\u8ff4\u5708\u6642\u5efa\u7acb\uff0c\u4e26\u5728\u8a08\u7b97\u904e\u7a0b\u4e2d\u5132\u5b58<\/p>\n\n\n

    \nn = int(input()) #\u8f38\u5165n\nmaxNum,minNum = 0,401 #\u6700\u5c0f\u503c\u5fc50\uff0c\u6700\u5927\u503c\u5fc5400\nx1,y1 = map(int,input().split()) #\u7b2c\u4e00\u5c0d\u6578\u5b57\nfor i in range(1,n): \n    x2,y2 = map(int,input().split()) #\u7b2c\u4e8c\u5c0d\u6578\u5b57\n    temp = abs(x2-x1)+abs(y2-y1) #\u66fc\u54c8\u9813\u8ddd\u96e2\u516c\u5f0f\n    maxNum = max(maxNum,temp) #\u627e\u6700\u5927\u503c\n    minNum = min(minNum,temp) #\u627e\u6700\u5c0f\u503c\n    x1,y1 = x2,y2 #\u7b2c\u4e8c\u5c0d\u6578\u5b57\u8b8a\u6210\u7b2c\u4e00\u5c0d\u6578\u5b57\nprint(maxNum,minNum) #\u8f38\u51fa\n<\/pre><\/div>\n\n\n
    \u4ee5\u4e0a\u70ba\u89e3\u984c\u904e\u7a0b\uff0c\u82e5\u6709\u4efb\u4f55\u610f\u898b\u6b61\u8fce\u7559\u8a00\u3002<\/p>\n\n\n\n
    \u904b\u8ca8\u7ad9<\/h2>\n\n\n\n
    Youtube\u8b1b\u89e3\u5f71\u7247<\/a><\/p>\n\n\n\n
    \u984c\u9762\u7c21\u8ff0\uff1a
    \u5171\u6709n\u500b\u8ca8\u7269\uff0c\u5176\u4e2d\u8ca8\u7269\u6709\u4e94\u7a2e\u4e0d\u540c\u7684\u578b\u72c0\uff0c\u5206\u5225\u70baA\u3001B\u3001C\u3001D\u3001E\u3002<\/p>\n\n\n\n
    \"APCS\u300c\u904b\u8ca8\u7ad9\u300dA\u3001B\u3001C\u3001D\u3001E\u4e94\u7a2e\u8ca8\u7269\"
    <\/p>\n\n\n\n
    \u8981\u5c07\u9019\u4e9b\u8ca8\u7269\u653e\u7f6e\u5728 R x C \u7684\u5009\u5eab\u88e1\u9762\uff0c\u653e\u7f6e\u6642\u6703\u544a\u77e5\u7a2e\u985e<\/span>\u4ee5\u53ca\u8207\u5929\u82b1\u677f\u7684\u8ddd\u96e2<\/span>\uff0c\u63a5\u8457\u8981\u63a8\u5230\u5009\u5eab\u7684\u6700\u5de6\u7aef
    \u653e\u7f6e\u4e26\u4e14\u8207\u5929\u82b1\u677f\u7684\u8ddd\u96e2\u5fc5\u9808\u7dad\u6301\u4e00\u81f4\u3002\u82e5\u4e0d\u80fd\u5b8c\u6574\u653e\u7f6e\u81f3\u5009\u5eab\u5247\u4e1f\u68c4\u3002<\/p>\n\n\n\n
    \u6700\u5f8c\u8981\u8f38\u51fa\u5009\u5eab\u5269\u4e0b\u591a\u5c11\u7a7a\u4f4d<\/span>\u4ee5\u53ca\u88ab\u907a\u68c4\u7684\u8ca8\u7269\u6578\u91cf<\/span>\u3002<\/p>\n\n\n\n
    \u9019\u984c\u7684\u91cd\u9ede\u5176\u5be6\u5728\u65bc\u5b50\u984c\u7684\u5206\u6578\u914d\u7f6e\uff0c\u524d20%\u70ba\u53ea\u6709 B \u7684\u72c0\u6cc1\uff0c40%\u70ba\u6709 A\u3001B\u3001C \u7684\u72c0\u6cc1\uff0c\u6700\u5f8c40%\u624d\u662f\u5168\u90e8\u90fd\u6709\u7684\u72c0\u6cc1\u3002<\/p>\n\n\n\n
    \u6b64\u6642\u7a0d\u5fae\u601d\u8003\u4e00\u4e0b\u6703\u6709\u4e9b\u767c\u73fe\u3002<\/p>\n\n\n\n
    \"APCS\"
    \u53ea\u6709B\u7684\u6642\u5019<\/figcaption><\/figure>\n\n\n\n
    \u7576\u53ea\u6709B\u7684\u6642\u5019\u57fa\u672c\u4e0a\u4f86\u8aaa\u6703\u628a\u6240\u6709\u7a7a\u683c\u586b\u6eff(\u9664\u4e86\u8d85\u51fa\u7bc4\u570d\u7684)\uff0c\u6240\u4ee5\u4e0d\u5fc5\u8981\u53bb\u8a08\u7b97\u6700\u5de6\u908a\u7684\u5009\u5eab\u5269\u4e0b\u90a3\u4e9b\u7a7a\u683c\u3002<\/p>\n\n\n\n
    \"APCS\"
    \u6709A\u3001B\u3001C\u7684\u6642\u5019<\/figcaption><\/figure>\n\n\n\n
    \u9019\u6642\u5019\u958b\u59cb\u51fa\u73fe\u7a7a\u683c\u4e86\uff0c\u6bcf\u7576\u964d\u843d\u6642\u5c31\u5fc5\u9808\u8981\u8a08\u7b97\u6240\u6703\u9020\u6210\u7684\u7a7a\u683c\uff0c\u4f46\u81f3\u5c11\u9084\u662f\u540c\u4e00\u500b\u5e73\u9762\u9084\u597d\u8655\u7406\u3002<\/p>\n\n\n\n
    \"APCS\"
    \u5168\u90e8\u90fd\u6709\u7684\u6642\u5019<\/figcaption><\/figure>\n\n\n\n
    \u7576\u6709D\u8207E\u6642\u5c31\u6703\u6bd4\u8f03\u9ebb\u7169\uff0c\u5fc5\u9808\u5728\u589c\u843d\u5f8c\u53bb\u5224\u65b7\u5230\u5e95\u662f\u5f80\u53f3\u63a8\u79fb3\u683c2\u683c\u9084\u662f1\u683c\u3002<\/p>\n\n\n\n
    \u6709\u4e86\u4ee5\u4e0a\u6982\u5ff5\u4e4b\u5f8c\u4f86\u7a0d\u5fae\u601d\u8003\u4e00\u4e0b\u89e3\u984c\u6b65\u9a5f\uff1a
    1. \u8f38\u51651\uff1a\u4e09\u500b\u6578\u5b57 R C N\uff0cR \u8ddf C \u5c31\u662f\u5bec\u8ddf\u9ad8\uff0cN\u662f\u8ca8\u7269\u6578\u91cf\u3002
    2. \u8f38\u51652\uff1afor i in range(N)\uff0c\u7528\u4f86\u8f38\u5165\u8ca8\u7269\u7a2e\u985e\u8207\u9802\u90e8\u7684\u8ddd\u96e2\u3002
    3. \u908f\u8f2f1\uff1a\u7d00\u9304\uff0c\u9019\u984c\u7684\u91cd\u9ede\u5728\u65bc\u5982\u4f55\u8a18\u9304\uff0c\u5982\u679c\u5c0d\u9019\u6bd4\u8f03\u4e0d\u64c5\u9577\u7684\u6216\u8a31\u53ef\u4ee5\u4f7f\u7528matrix\u7d00\u9304\uff0c\u4f46\u500b\u4eba\u53ea\u7528\u4e00\u689darray\u7d00\u9304\uff0c\u5c08\u9580\u8a18\u9304\u8207\u5009\u5eab\u5de6\u7aef\u7684\u8ddd\u96e2\u3002
    4. \u908f\u8f2f2\uff1a\u7d71\u8a08\u7a7a\u767d\uff0c\u770b\u8981\u7528\u52a0\u6cd5\u9084\u662f\u6e1b\u6cd5\uff0c\u6e1b\u6cd5\u6703\u76f8\u5c0d\u800c\u8a00\u7c21\u55ae\u4e00\u4e9b\u3002
    5. \u8f38\u51fa\uff1a\u4ee5\u4e0a\u90fd\u6709\u597d\u597d\u505a\u7684\u8a71\u57fa\u672c\u4e0a\u6c92\u4ec0\u9ebc\u56f0\u96e3\u7684<\/p>\n\n\n\n
    \u500b\u4eba\u5728\u8003\u8a66\u6642\u6703\u5148\u5b8c\u6210\u7b2c\u4e00\u5b50\u984c\u8207\u7b2c\u4e8c\u5b50\u984c\u62ff\u901960\u5206\u5373\u53ef\uff0c\u7b2c\u4e09\u5b50\u984c\u7b49\u5f8c\u9762\u984c\u76ee\u5b8c\u6210\u518d\u56de\u4f86\u505a\u3002<\/p>\n\n\n
    \nblock = { #\u5bec, \u9ad8, \u683c\u5b50\u6578\n    "A": (1, 4, 4),\n    "B": (3, 1, 3),\n    "C": (2, 2, 4),\n    "D": (3, 2, 4),\n    "E": (2, 3, 5)\n}\n\nr, c, n = map(int, input().split())\ntotal_block = r*c #\u7e3d\u7a7a\u683c\u6578\nout = 0 #\u8981\u88ab\u4e1f\u6389\u7684\u8ca8\u7269\nrow = [0 for i in range(r)] #\u8a08\u7b97\u8ddd\u96e2\nfor i in range(n):\n    block_type, top = input().split() #\u8ca8\u7269\u7a2e\u985e\u3001\u5929\u82b1\u677f\u8ddd\u96e2\n    top = int(top)\n    bottom = top + block[block_type][1]\n    clone_row = row[:][top:bottom] #\u9019\u908a\u8981deepclone\u5426\u5247\u6703\u6539\u5230\u539f\u8cc7\u6599\n    for index in range(block[block_type][1]): #D\u8ddfE\u6bd4\u8f03\u9ebb\u7169\u8981\u62c9\u51fa\u4f86\u7b97\n        if block_type == 'D' and index == 0:\n            clone_row[index] += 1\n        elif block_type == 'E' and index == 0:\n            clone_row[index] += 1\n        else:\n            clone_row[index] += block[block_type][0]\n    max_R = max(clone_row)\n    if max_R > c: #\u5224\u65b7\u8a72\u8ca8\u7269\u662f\u5426\u8981\u88ab\u4e1f\u68c4\n        out += 1\n    else:\n        row[top:bottom] = [max_R for j in range(block[block_type][1])] \n        #\u78ba\u5b9a\u6700\u7d42\u9ad8\u5ea6\u518d\u4e00\u8d77\u6539\u56de\u5230\u539frow\n        total_block -= block[block_type][2]\nprint(total_block, out)\n\n<\/pre><\/div>\n\n\n
    \u4ee5\u4e0a\u70ba\u89e3\u984c\u904e\u7a0b\uff0c\u82e5\u6709\u4efb\u4f55\u610f\u898b\u6b61\u8fce\u7559\u8a00\u3002<\/p>\n\n\n\n
    \u77f3\u7a9f\u63a2\u96aa<\/h2>\n\n\n\n
    Youtube\u8b1b\u89e3\u5f71\u7247<\/a><\/p>\n\n\n\n
    \u984c\u76ee\u7c21\u8ff0\uff1a
    \u6709 n \u500b\u77f3\u7a9f\u5f62\u6210\u6a39\u72c0\u7d50\u69cb\uff0c\u6bcf\u500b\u77f3\u7a9f\u90fd\u6703\u6709\u4e00\u500b val \uff0c\u82e5\u6b64 val \u70ba\u5076\u6578\u5247\u6709 2 \u500b\u5206\u652f\uff0c\u5947\u6578\u5247\u70ba 3 \u500b\u5206\u652f\u3002\u53d6\u6240\u6709\u76f8\u9130\u7684\u5169\u500b\u77f3\u7a9f\u7684 val \u9032\u884c\u6e1b\u6cd5\u53d6\u7d55\u5c0d\u503c\u7684\u7e3d\u548c\u3002<\/p>\n\n\n\n
    \u91cd\u9ede\u662f\u8981\u5982\u4f55\u77e5\u9053\u6b64\u5169\u6578\u662f\u76f8\u9130\u7684\uff0c\u984c\u76ee\u6240\u7d66\u4e88\u7684\u6578\u5217\u662f\u5df2\u7d93\u900f\u904e preorder traversal\u904e\u7684\u7d50\u679c\u3002\u6240\u4ee5\u53ea\u8981\u63a5\u8457\u4ed6\u7684\u7d50\u679c\u505a dfs <\/span>\u5373\u53ef\u3002<\/p>\n\n\n\n
    \u6709\u4e86\u4ee5\u4e0a\u6982\u5ff5\u4e4b\u5f8c\u4f86\u7a0d\u5fae\u601d\u8003\u4e00\u4e0b\u89e3\u984c\u6b65\u9a5f\uff1a
    1. \u8f38\u5165\uff1a\u6578\u5217\u5207\u5272\u8f49\u6574\u6578
    2. \u908f\u8f2f\uff1a\u905e\u8ff4+\u5224\u65b7 val \u5947\u5076\u6578\u6c7a\u5b9a\u63a5\u4e0b\u4f86\u8981\u8d70\u7684\u7bc0\u9ede<\/p>\n\n\n\n
    \"APCS
    \u82e5\u8f38\u5165\u7684\u6578\u5b57\u70ba 2 4 0 5 0 0 0 6 0 0<\/p>\n\n\n
    \nnumList = list(map(int,input().split()))\nans,index = 0,1\n#\u56e0\u70baindex\u5fc5\u9808\u5f80\u4e0b\u8b80\u53d6numList\u7684\u6771\u897f\n#\u6240\u4ee5global\u6bd4\u8f03\u65b9\u4fbf\uff0cans\u4ea6\u540c(\u6216\u7528list\u4e5f\u53ef\u4ee5)\ndef run(num):\n    global index,ans\n    for i in range(num%2+2):#\u5076\u6578\u7bc0\u9ede\u8dd1\u5169\u500b\uff0c\u5947\u6578\u8dd1\u4e09\u500b\n        val = numList[index]\n        index+=1\n        if val == 0:#\u9047\u5230\u7a7a\u7bc0\u9ede\n            continue\n        ans+=abs(num-val)#\u8a08\u7b97\u76f8\u9130\n        run(val)\nrun(numList[0])\nprint(ans)\n<\/pre><\/div>\n\n\n
    \u4ee5\u4e0a\u70ba\u89e3\u984c\u904e\u7a0b\uff0c\u82e5\u6709\u4efb\u4f55\u610f\u898b\u6b61\u8fce\u7559\u8a00\u3002<\/p>\n\n\n\n
    \u84cb\u6b65\u9053<\/h2>\n\n\n\n
    Youtube\u8b1b\u89e3\u5f71\u7247<\/a><\/p>\n\n\n\n
    \u984c\u76ee\u7c21\u8ff0\uff1a
    \u7d66\u4e00\u500b n x n \u7684\u65b9\u5f62\u5340\u57df\uff0c\u6bcf\u4e00\u500b\u90fd\u6709\u6574\u6578 h \u4ee3\u8868\u6d77\u62d4\u9ad8\u5ea6\u3002\u60f3\u8fa6\u6cd5\u5f9e\u5de6\u4e0a\u89d2\u8d70\u5230\u53f3\u4e0b\u89d2\uff0c\u6bcf\u4e00\u6b65\u7684\u9ad8\u4f4e\u843d\u5dee\u8d8a\u5c0f\u8d8a\u597d\u3002\u6700\u5f8c\u8981\u6c42\u51fa\u6700\u5c0f\u7684\u6700\u5927\u9ad8\u5ea6\u5dee\uff0c\u4ee5\u53ca\u7528\u6b64\u65b9\u6848\u6240\u8d70\u51fa\u4f86\u7684\u8def\u5f91\u9577\u3002<\/p>\n\n\n\n
    \u9019\u984c\u984c\u76ee\u5176\u5be6\u6eff\u597d\u7406\u89e3\u7684\uff0c\u91cd\u9ede\u662f\u5f8c\u7e8c\u8981\u5982\u4f55\u8655\u7406\u3002<\/p>\n\n\n\n
    \"\"
    \u7531\u4e0a\u5716\u53ef\u77e5\u82e5\u8d70 3 -> 3 -> 4 -> 5 -> 6 \uff0c\u53ef\u4ee5\u5f97\u5230\u7684\u6700\u5c0f\u7684\u6700\u5927\u9ad8\u5ea6\u5dee\u70ba1\uff0c\u800c\u8def\u5f91\u9577\u70ba4\u3002<\/figcaption><\/figure>\n\n\n\n
    \"\"
    \u7531\u4e0a\u5716\u53ef\u77e5\u82e5\u8d70 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 \uff0c\u53ef\u4ee5\u5f97\u5230\u7684\u6700\u5c0f\u7684\u6700\u5927\u9ad8\u5ea6\u5dee\u70ba0\uff0c\u800c\u8def\u5f91\u9577\u70ba16\u3002<\/figcaption><\/figure>\n\n\n\n
    \u6709\u4e86\u4ee5\u4e0a\u6982\u5ff5\u4e4b\u5f8c\u4f86\u7a0d\u5fae\u601d\u8003\u4e00\u4e0b\u89e3\u984c\u6b65\u9a5f\uff1a
    1. \u8f38\u51651\uff1a\u4e00\u6578\u5b57 n \u4ee3\u8868\u6b64\u65b9\u578b\u5340\u57df\u7684\u908a\u9577\u3002
    2. \u8f38\u51652\uff1a\u591a\u500b\u6574\u6578\uff0c\u6574\u6578\u8207\u6574\u6578\u9593\u6709\u7a7a\u683c\uff0c\u4ee3\u8868\u6bcf\u4e00\u683c\u7684\u9ad8\u5ea6\u3002
    3. \u908f\u8f2f1\uff1a\u9996\u5148\u8981\u627e\u51fa\u6700\u5c0f\u7684\u6700\u5927\u9ad8\u5ea6\u5dee -> \u4e8c\u641c\u6216Dijkstra
    4. \u908f\u8f2f2\uff1a\u5229\u7528\u6b64\u9ad8\u5ea6\u5dee\u8dd1BFS\u78ba\u8a8d\u8def\u5f91
    5. \u8f38\u51fa\uff1a\u5c31\uff0c\u8f38\u51fa\u3002<\/p>\n\n\n
    \nfrom collections import deque\nimport heapq\nn = int(input())\nmatrix = []#\u5b58\u9ad8\u5ea6\nmovement = ((1,0),(0,1),(-1,0),(0,-1)) #\u8dd1\u4f4d\u79fb\u7528\nfor i in range(n):\n    matrix.append(list(map(int,input().split())))\ntable = [[0 for i in range(n)] for i in range(n)] #\u7d00\u9304\u8def\u5f91\ncashs = [[10**6 for i in range(n)] for i in range(n)] #\u7d00\u9304\u9ad8\u4f4e\u5dee\nheap = [(0,0,0)] #\u7528heap\u5b58\u5ea7\u6a19\u8207\u9ad8\u4f4e\u5dee\nwhile heap:\n    x,y,cash = heapq.heappop(heap)\n    for i in movement: #\u5ea7\u6a19\n        newX,newY = x + i[0],y + i[1]\n        if n>newX>=0 and n>newY>=0:\n            nextCash = max(cash,abs(matrix[newX][newY] - matrix[x][y]))\n            if cashs[newX][newY] > nextCash: \n                cashs[newX][newY] = nextCash\n                heapq.heappush(heap,(newX,newY,nextCash)) #\u9ad8\u4f4e\u5dee\u7d00\u9304\nprint(cashs[-1][-1])\nqueue = deque()\nqueue.append((0,0,1))#\u5ea7\u6a19\u3001\u8def\u5f91\nwhile queue:\n    x,y,temp = queue.popleft()\n    if table[x][y]:#\u8d70\u904e\u4e0d\u8d70\n        continue\n    table[x][y] = temp\n    for i in movement:\n        newX,newY = x + i[0],y + i[1]\n        if n>newX>=0 and n>newY>=0 and abs(matrix[newX][newY] - matrix[x][y]) <= cashs[-1][-1]:\n            queue.append((newX,newY,temp+1))\nprint(table[-1][-1]-1)#\u5229\u7528\u6700\u5c0f\u7684\u6700\u5927\u9ad8\u5ea6\u5dee\u5fc5\u53ef\u4ee5\u8d70\u5b8c\u5168\u7a0b\n<\/pre><\/div>\n\n\n
    \n
    \u524d\u5f80 Python \u5bc6\u96c6\u57fa\u790e\u9060\u8ddd\u73ed <\/span><\/a><\/div>\n<\/div><\/div>\n\n\n\n
    \u4ee5\u4e0a\u70ba\u89e3\u984c\u904e\u7a0b\uff0c\u82e5\u6709\u4efb\u4f55\u610f\u898b\u6b61\u8fce\u7559\u8a00\u3002<\/p>\n\n\n\n
    \u63a8\u85a6\u95b1\u8b80\uff1a<\/em>\u7a0b\u5f0f\u8a9e\u8a00\u767e\u767e\u7a2e\uff0c\u70ba\u4ec0\u9ebcPython\u662f\u5beb\u4eba\u5de5\u667a\u6167\u7684\u7b2c1\u9078\u64c7\uff1f<\/a><\/p>\n\n\n\n
    \u63a8\u85a6\u95b1\u8b80\uff1a<\/em>APCS, Roblox, Python, C++ \u7a0b\u5f0f\u8a9e\u8a00\u9019\u9ebc\u591a\u600e\u9ebc\u9078\uff1f \u5b69\u5b50\u5b78\u7a0b\u5f0f\u5e38\u898b5\u5927\u554f\u984c\u89e3\u7b54<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    \u672c\u6b21\u984c\u76ee\u57fa\u672c\u4e0a\u4f86\u8aaa\u7b97\u662f\u6bd4\u8f03\u55ae\u7d14\u7684\u3002\u7b2c\u4e00\u984c\u662f\u70ba\u8fed\u4ee3\u7684\u57fa\u672c\u984c\uff0c\u4ee5\u53ca\u5982\u4f55\u5728\u591a\u500b\u6578\u5b57\u4e2d\u627e\u51fa\u6700\u5927\u6700\u5c0f\u503c\u3002\u7b2c\u4e8c\u984c\u662f\u6a21\u64ec\u984c\uff0c\u8003\u9a57\u5c0d\u65bc\u4e0d\u540c\u60c5\u5883\u4e0b\u7684\u8655\u7406\u65b9\u5f0f\u8207\u908f\u8f2f…….<\/p>\n","protected":false},"author":12,"featured_media":3460,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[1],"tags":[177,176,39,75],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":6}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2022\/10\/25336-2500x1667.jpg?fit=2500%2C1667&ssl=1","_links":{"self":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/3410"}],"collection":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/comments?post=3410"}],"version-history":[{"count":38,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/3410\/revisions"}],"predecessor-version":[{"id":3891,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/3410\/revisions\/3891"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/media\/3460"}],"wp:attachment":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/media?parent=3410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/categories?post=3410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/tags?post=3410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}