{"id":65,"date":"2024-01-31T02:06:29","date_gmt":"2024-01-30T18:06:29","guid":{"rendered":"https:\/\/www.nenuacm.top\/?p=65"},"modified":"2024-02-08T22:30:59","modified_gmt":"2024-02-08T14:30:59","slug":"2024-1-27-dfs-bfs","status":"publish","type":"post","link":"https:\/\/www.nenuacm.top\/index.php\/2024\/01\/31\/2024-1-27-dfs-bfs\/","title":{"rendered":"2024.1.27 DFS + BFS"},"content":{"rendered":"\n

A – \u68cb\u76d8\u95ee\u9898<\/h1>\n\n\n\n

\u9898\u76ee\uff1a<\/h2>\n\n\n\n
\n

\u5728\u4e00\u4e2a\u7ed9\u5b9a\u5f62\u72b6\u7684\u68cb\u76d8\uff08\u5f62\u72b6\u53ef\u80fd\u662f\u4e0d\u89c4\u5219\u7684\uff09\u4e0a\u9762\u6446\u653e\u68cb\u5b50\uff0c\u68cb\u5b50\u6ca1\u6709\u533a\u522b\u3002\u8981\u6c42\u6446\u653e\u65f6\u4efb\u610f\u7684\u4e24\u4e2a\u68cb\u5b50\u4e0d\u80fd\u653e\u5728\u68cb\u76d8\u4e2d\u7684\u540c\u4e00\u884c\u6216\u8005\u540c\u4e00\u5217\uff0c\u8bf7\u7f16\u7a0b\u6c42\u89e3\u5bf9\u4e8e\u7ed9\u5b9a\u5f62\u72b6\u548c\u5927\u5c0f\u7684\u68cb\u76d8\uff0c\u6446\u653ek\u4e2a\u68cb\u5b50\u7684\u6240\u6709\u53ef\u884c\u7684\u6446\u653e\u65b9\u6848C\u3002<\/p>\n\n\n\n

Input<\/h3>\n\n\n\n

\u8f93\u5165\u542b\u6709\u591a\u7ec4\u6d4b\u8bd5\u6570\u636e\u3002 \u6bcf\u7ec4\u6570\u636e\u7684\u7b2c\u4e00\u884c\u662f\u4e24\u4e2a\u6b63\u6574\u6570\uff0cn k\uff0c\u7528\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\uff0c\u8868\u793a\u4e86\u5c06\u5728\u4e00\u4e2an*n\u7684\u77e9\u9635\u5185\u63cf\u8ff0\u68cb\u76d8\uff0c\u4ee5\u53ca\u6446\u653e\u68cb\u5b50\u7684\u6570\u76ee\u3002 n <= 8 , k <= n \u5f53\u4e3a-1 -1\u65f6\u8868\u793a\u8f93\u5165\u7ed3\u675f\u3002 \u968f\u540e\u7684n\u884c\u63cf\u8ff0\u4e86\u68cb\u76d8\u7684\u5f62\u72b6\uff1a\u6bcf\u884c\u6709n\u4e2a\u5b57\u7b26\uff0c\u5176\u4e2d # \u8868\u793a\u68cb\u76d8\u533a\u57df\uff0c . \u8868\u793a\u7a7a\u767d\u533a\u57df\uff08\u6570\u636e\u4fdd\u8bc1\u4e0d\u51fa\u73b0\u591a\u4f59\u7684\u7a7a\u767d\u884c\u6216\u8005\u7a7a\u767d\u5217\uff09\u3002<\/p>\n\n\n\n

Output<\/h3>\n\n\n\n

\u5bf9\u4e8e\u6bcf\u4e00\u7ec4\u6570\u636e\uff0c\u7ed9\u51fa\u4e00\u884c\u8f93\u51fa\uff0c\u8f93\u51fa\u6446\u653e\u7684\u65b9\u6848\u6570\u76eeC \uff08\u6570\u636e\u4fdd\u8bc1C<2^31\uff09\u3002<\/p>\n\n\n\n

nenu \u84dd\u6865\u676f\u8bad\u7ec3\u8d5b\uff08dfs+bfs\uff09 – Virtual Judge (vjudge.net)<\/a><\/p>\n<\/blockquote>\n\n\n\n

\u601d\u8def\uff1a<\/h2>\n\n\n\n

\u8fd9\u9053\u9898\u7684\u9898\u610f\u4e0d\u96be\u7406\u89e3\uff0c\u6211\u4eec\u8981\u6c42\u6240\u6709\u7684\u6446\u653e\u60c5\u51b5\uff0c\u5bf9\u4e8e\u8fd9\u4e2a\u95ee\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u7528dfs\u548cbfs\u90fd\u53ef\u4ee5\uff0c\u56e0\u4e3a\u6bcf\u4e00\u79cd\u53ef\u80fd\u7684\u6446\u653e\u90fd\u8981\u5c1d\u8bd5\u3002<\/p>\n\n\n\n

\u6211\u4eec\u4ece\u5934\u5f00\u59cb\u904d\u5386\uff0c\u7136\u540e\u9047\u5230\u4e00\u4e2a\u7b26\u5408\u7684\u60c5\u51b5\u5c31\u5c1d\u8bd5\u653e\u8fdb\u53bb\uff0c\u7136\u540eDFS\uff0c\u7528vis\u6570\u7ec4\u8bb0\u5f55\u6bcf\u4e2a\u70b9\u641c\u7d22\u7684\u70b9\uff0c\u641c\u7d22\u5230\u7684\u70b9\u8981\u505a\u6807\u8bb0\uff0c\u8868\u793a\u8fd9\u4e00\u884c\u548c\u8fd9\u4e00\u5217\u4e0d\u518d\u8003\u8651\u5176\u5b83\u7684\u70b9\u3002<\/p>\n\n\n\n

\u4ee3\u7801\u8fd8\u662f\u5f88\u597d\u7406\u89e3\u7684\uff08\u5c3d\u7ba1\u5b9e\u73b0\u8d77\u6765\u4e00\u76f4\u51fabug\uff09<\/del>\u3002<\/p>\n\n\n\n

\u4ee3\u7801DFS\uff1a<\/h2>\n\n\n\n
#include<iostream>\n#include<string.h>\nusing namespace std;\nint mx[1005][1005];\nint n,k;\nint ans;\nint vis[1005];\n\nvoid dfs(int l,int step){\n    if(step == k){\n        ans++;\n        return ;\n    }\n    for(int i = l;i <= n;i++){\n        for(int j = 1;j <= n;j++){\n            \/\/\u627e\u5230\u53ef\u4ee5\u653e\u7684\uff0c\u5e76\u4e14\u6ca1\u88ab\u5360\u636e\n            if(mx[i][j] == 1 && vis[j] == 0){\n                vis[j] = 1;\n                dfs(i + 1,step + 1);\n                vis[j] = 0;\n            }\n        }\n    }\n}\nint main(){\n    \n    while(cin >> n >> k){\n        ans = 0;\n        memset(vis,0,sizeof(vis));\n        if(n == -1 && k == -1) break;\n        \n        for(int i = 1;i <= n;i++){\n            for(int j = 1;j <= n;j++){\n                char c;\n                cin >> c;\n                if(c == '.') mx[i][j] = 0;\n                else mx[i][j] = 1;\n            }\n        }\n        dfs(1,0);\n        cout << ans << \"\\n\";\n    }\n} <\/code><\/pre>\n\n\n\n
B – Dungeon Master \u5730\u7262\u4e3b<\/h1>\n\n\n\n
\u9898\u76ee\uff1a<\/h2>\n\n\n\n
\n
\u4f60\u88ab\u56f0\u5728\u4e00\u4e2a\u4e09\u7ef4\u5730\u7262\u4e2d\uff0c\u9700\u8981\u627e\u5230\u6700\u5feb\u7684\u51fa\u8def\uff01\u8fd9\u4e2a\u5730\u7262\u7531\u5355\u5143\u7acb\u65b9\u4f53\u7ec4\u6210\uff0c\u8fd9\u4e9b\u7acb\u65b9\u4f53\u53ef\u80fd\u5145\u6ee1\u4e86\u5ca9\u77f3\uff0c\u4e5f\u53ef\u80fd\u6ca1\u6709\u3002\u4f60\u6bcf\u79fb\u52a8\u4e00\u4e2a\u5355\u4f4d\u5411\u5317\u3001\u5357\u3001\u4e1c\u3001\u897f\u3001\u4e0a\u6216\u4e0b\u9700\u8981\u4e00\u5206\u949f\u3002\u4f60\u4e0d\u80fd\u5bf9\u89d2\u79fb\u52a8\uff0c\u8ff7\u5bab\u56db\u9762\u90fd\u88ab\u575a\u56fa\u7684\u5ca9\u77f3\u6240\u5305\u56f4\u3002<\/p>\n\n\n\n
\u662f\u5426\u6709\u53ef\u80fd\u9003\u8131\uff1f\u5982\u679c\u6709\uff0c\u9700\u8981\u591a\u957f\u65f6\u95f4\uff1f<\/p>\n\n\n\n
Input<\/h3>\n\n\n\n
\u8f93\u5165\u5305\u62ec\u591a\u4e2a\u5730\u7262\u7684\u63cf\u8ff0\u3002\u6bcf\u4e2a\u5730\u7262\u7684\u63cf\u8ff0\u5f00\u59cb\u4e8e\u4e00\u884c\uff0c\u5305\u542b\u4e09\u4e2a\u6574\u6570L\u3001R\u548cC\uff08\u6240\u6709\u7684\u6570\u503c\u90fd\u9650\u5236\u572830\u4ee5\u5185\uff09\u3002 L\u662f\u6784\u6210\u5730\u7262\u7684\u5c42\u6570\u3002 R\u548cC\u662f\u6784\u6210\u6bcf\u4e00\u5c42\u5e73\u9762\u56fe\u7684\u884c\u6570\u548c\u5217\u6570\u3002 \u7136\u540e\u4f1a\u8ddf\u968fL\u5757R\u884c\u6bcf\u884cC\u4e2a\u5b57\u7b26\u3002\u6bcf\u4e2a\u5b57\u7b26\u63cf\u8ff0\u5730\u7262\u7684\u4e00\u4e2a\u5355\u5143\u683c\u3002\u5145\u6ee1\u5ca9\u77f3\u7684\u5355\u5143\u683c\u7528’#’\u8868\u793a\uff0c\u7a7a\u5355\u5143\u683c\u7528’.’\u8868\u793a\u3002\u4f60\u7684\u8d77\u59cb\u4f4d\u7f6e\u7528’S’\u8868\u793a\uff0c\u51fa\u53e3\u7528\u5b57\u6bcd’E’\u8868\u793a\u3002\u6bcf\u5c42\u540e\u9762\u6709\u4e00\u4e2a\u7a7a\u884c\u3002\u8f93\u5165\u4ee5L\u3001R\u548cC\u4e09\u4e2a\u96f6\u7ed3\u675f\u3002<\/p>\n\n\n\n
Output<\/h3>\n\n\n\n
\u6bcf\u4e2a\u8ff7\u5bab\u751f\u6210\u4e00\u884c\u8f93\u51fa\u3002\u5982\u679c\u80fd\u591f\u5230\u8fbe\u51fa\u53e3\uff0c\u6253\u5370\u4e00\u884c\u5f62\u5f0f\u5982\u4e0b\u7684\u5185\u5bb9 Escaped in x minute(s)\u3002<\/p>\n\n\n\n
\u5176\u4e2dx\u88ab\u66ff\u6362\u4e3a\u9003\u8131\u6240\u9700\u7684\u6700\u77ed\u65f6\u95f4\u3002 \u5982\u679c\u65e0\u6cd5\u9003\u8131\uff0c\u6253\u5370\u884c Trapped!<\/p>\n\n\n\n
nenu \u84dd\u6865\u676f\u8bad\u7ec3\u8d5b\uff08dfs+bfs\uff09 – Virtual Judge (vjudge.net)<\/a><\/p>\n<\/blockquote>\n\n\n\n
\u601d\u8def\uff1a<\/h2>\n\n\n\n
\u8fd9\u9053\u9898\u5c31\u662f\u7ed9\u4e00\u4e2a\u4e09\u7ef4\u7684\u8ff7\u5bab\uff0c\u7136\u540e\u4ece\u8d77\u59cb\u70b9\u8d70\u5230\u7ec8\u70b9\u3002\u672c\u8d28\u4e0a\u6765\u8bf4\uff0c\u548c\u4e8c\u7ef4\u5730\u56fe\u7684\u904d\u5386\u6ca1\u6709\u4ec0\u4e48\u533a\u522b\uff0c\u5c31\u662f\u591a\u4e86\u4e00\u7ef4\u800c\u5df2\uff0c\u5f00\u4e2a\u4e09\u7ef4\u6570\u7ec4\u5c31\u884c\u3002\u8fd9\u9053\u9898\u56e0\u4e3a\u662f\u6c42\u6700\u77ed\u65f6\u95f4\uff0c\u5982\u679c\u7528DFS\u7684\u8bdd\u4f1a\u628a\u6240\u6709\u60c5\u51b5\u90fd\u8003\u8651\u4e00\u904d\uff0c\u65f6\u95f4\u4f1a\u5f88\u6162\uff0c\u5f88\u53ef\u80fdTLE\uff0c\u6240\u4ee5\u6211\u4eec\u91c7\u7528BFS\u6765\u641c\u7d22\u3002\u7136\u540e\u5c31\u662fBFS\u7684\u677f\u5b50\u4e86\uff0c\u6ca1\u6709\u4ec0\u4e48\u7279\u522b\u7684\uff0c\u5c31\u662f\u7279\u5224\u7684\u65f6\u5019\u6ce8\u610f\u4e00\u70b9\u3002\u7136\u540e\u4e3a\u4e86\u9632\u6b62\u91cd\u590d\u8d70\uff0c\u9700\u8981\u5f00\u4e2avis\u6570\u7ec4\u8bb0\u5f55\u8d70\u8fc7\u7684\u5730\u65b9\uff08\u8d70\u8ff7\u5bab\u4e0d\u9700\u8981\u91cd\u590d\u8d70\uff09\u3002\u7136\u540e\u7ed3\u6784\u4f53\u5728\u51fd\u6570\u91cc\u521b\u5efa\u7684\u65f6\u5019\u662f\u6ca1\u6709\u521d\u59cb\u5316\u7684\uff0c\u6240\u4ee5\u9700\u8981\u81ea\u884c\u521d\u59cb\u5316\u6bcf\u4e00\u4e2a\u53d8\u91cf\u3002<\/strong><\/p>\n\n\n\n
\u4ee3\u7801BFS\uff1a<\/h2>\n\n\n\n
#include<iostream>\n#include<queue>\n#include<cstring>\nusing namespace std;\nchar mp[35][35][35];\nint l,r,c;\ntypedef struct Node{\n    int x,y,z;\n    int step;\n}node;\nint s_x,s_y,s_z;\nint e_x,e_y,e_z;\nint flag;\nint mv[6][3] = {{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0}};\nint vis[35][35][35];\n\nvoid bfs(int x,int y,int z){\n    queue<node> q;\n    node start;\n    start.x = s_x;\n    start.y = s_y;\n    start.z = s_z;\n    start.step = 0;\/\/\u4e00\u5b9a\u8981\u521d\u59cb\u5316\n    q.push(start);\n    while(!q.empty()){\n        start = q.front();\n        q.pop();\n        if(start.x == e_x && start.y == e_y && start.z == e_z){\n            flag = start.step;\n            return ;\n        }\n        \/\/\u4e0a\u4e0b\u5de6\u53f3\u524d\u540e\u5730\u8d70,\u62d3\u5c55\u5b50\u8282\u70b9\n        for(int i = 0;i < 6;i++){\n            node child;\n            child.x = start.x + mv[i][0];\n            child.y = start.y + mv[i][1];\n            child.z = start.z + mv[i][2];\n            \/\/\u5982\u679c\u8d8a\u754c\n            if(child.x <= 0 || child.x > l || child.y <= 0 || child.y > r || child.z <= 0 || child.z > c){\n                continue;\n            }\n            \/\/\u5982\u679c\u662f\u5899\u58c1\n            if(mp[child.x][child.y][child.z] == '#') continue;\n            \/\/\u5982\u679c\u5df2\u7ecf\u8d70\u8fc7\u4e86\n            if(vis[child.x][child.y][child.z]) continue;\n            child.step = start.step + 1;\n            vis[child.x][child.y][child.z] = 1;\n            q.push(child);\n        }\n    }\n}\nint main(){\n\n    while(cin >> l >> r >> c){\n        if(l == 0 && r == 0 && c == 0) break;\n        memset(vis,0,sizeof(vis));\n        flag = 0;\n        for(int i = 1;i <= l;i++){\n            for(int j = 1;j <= r;j++){\n                for(int k = 1;k <= c;k++){\n                    cin >> mp[i][j][k];\n                    if(mp[i][j][k] == 'S'){\n                        s_x = i,s_y = j,s_z = k;\n                    }\n                    if(mp[i][j][k] == 'E'){\n                        e_x = i,e_y = j,e_z = k;\n                    }\n                }\n            }\n        }\n        bfs(s_x,s_y,s_z);\n        if(flag){\n            cout << \"Escaped in \" << flag << \" minute(s).\" << \"\\n\";\n        }else{\n            cout << \"Trapped!\" << \"\\n\";\n        }\n    }\n    \n} <\/code><\/pre>\n\n\n\n
C – Catch That Cow \u6293\u4f4f\u90a3\u5934\u725b<\/h1>\n\n\n\n
\u9898\u76ee\uff1a<\/h2>\n\n\n\n
\n
\u519c\u592b\u7ea6\u7ff0\u5f97\u77e5\u4e86\u4e00\u5934\u9003\u4ea1\u5976\u725b\u7684\u4f4d\u7f6e\uff0c\u4ed6\u60f3\u7acb\u5373\u6293\u4f4f\u5979\u3002\u4ed6\u4ece\u6570\u7ebf\u4e0a\u7684\u70b9N\uff080 \u2264 N \u2264 100,000\uff09\u51fa\u53d1\uff0c\u800c\u5976\u725b\u5728\u540c\u4e00\u6570\u7ebf\u4e0a\u7684\u70b9K\uff080 \u2264 K \u2264 100,000\uff09\u4e0a\u3002\u519c\u592b\u7ea6\u7ff0\u6709\u4e24\u79cd\u4ea4\u901a\u65b9\u5f0f\uff1a\u6b65\u884c\u548c\u4f20\u9001\u3002<\/p>\n\n\n\n