{"id":94,"date":"2022-11-21T20:37:10","date_gmt":"2022-11-21T12:37:10","guid":{"rendered":"https:\/\/forelink.top\/?p=94"},"modified":"2022-11-21T20:37:10","modified_gmt":"2022-11-21T12:37:10","slug":"%e6%90%9c%e7%b4%a2%e7%ae%97%e6%b3%95%e4%b8%8e%e5%9b%be%e8%ae%ba%ef%bc%88week-4-5%ef%bc%89","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2022\/11\/21\/%e6%90%9c%e7%b4%a2%e7%ae%97%e6%b3%95%e4%b8%8e%e5%9b%be%e8%ae%ba%ef%bc%88week-4-5%ef%bc%89\/","title":{"rendered":"\u641c\u7d22\u7b97\u6cd5\u4e0e\u56fe\u8bba\uff08Week 4 , 5\uff09"},"content":{"rendered":"\n

\u641c\u7d22\u548c\u52a8\u6001\u89c4\u5212\u662f\u7b97\u6cd5\u754c\u7684\u4e24\u5ea7\u5927\u5c71\u3002<\/p>\n\n\n\n

\u641c\u7d22\u672c\u8d28\u4e0a\u662f\u4e00\u79cd\u904d\u5386\uff0c\u662f\u5bf9\u6bcf\u4e00\u79cd\u60c5\u51b5\u64cd\u4f5c\u4e00\u904d\u3002<\/p>\n\n\n\n

T1 \u8ff7\u5bab\uff08dfs\uff09<\/h2>\n\n\n\n

\u662f\u597d\u9898\uff0c\u4e00\u9053\u7528dfs\u7684\u597d\u9898\u3002<\/p>\n\n\n\n

\n
\"\"<\/div><\/figure>\n<\/figure>\n\n\n\n
#include <iostream>\r\n#include <cstring>\r\nusing namespace std;\r\nint n,m,t;\r\nint movex[5]={0,1,0,-1,0};\/\/\u53f3 \u4e0a\r\nint movey[5]={0,0,-1,0,1};\/\/\u5de6 \u4e0b\r\nint world[15][15];\/\/\u56fe\r\nint vis[15][15];\/\/\u6807\u8bb0\r\nint sx,sy,fx,fy;\/\/\u8d77\u70b9 \u7ec8\u70b9\r\nint cnt;\/\/\u8ba1\u6570\u3002\r\nvoid dfs(int x,int y){\r\n\tif(x==fx&&y==fy){\r\n\t\tcnt++;\r\n\t\treturn;\r\n\t}\r\n\tfor(int i=1;i<=4;i++){\r\r\n\t\tint nx=x+movex[i];\r\n\t\tint ny=y+movey[i];\r\n\t\tif(world[nx][ny]==1&&vis[nx][ny]==0){\/\/\u53ef\u4ee5\u8d70\u5230\u3002\r\r\n\t\t\tvis[nx][ny]=1;\r\n\t\t\tdfs(nx,ny);\r\n\t\t\tvis[nx][ny]=0;\r\n\t\t}\r\n\t}\r\n}\r\nint main(){\r\n\tmemset(vis,0,sizeof(vis));\r\n\tmemset(world,0x3f,sizeof(world));\/\/\u9ed8\u8ba4\u4e0d\u80fd\u8d70\u3002\r\n\tcin>>n>>m>>t;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int l=1;l<=m;l++){\r\n\t\t\tworld[i][l]=1;\/\/\u53ef\u4ee5\u8d70\u7684\u3002\r\n\t\t}\r\n\t}\r\n\tcin>>sx>>sy>>fx>>fy;\r\n\tfor(int i=1;i<=t;i++){\r\n\t\tint x1,y1;\r\n\t\tcin>>x1>>y1;\r\n\t\tworld[x1][y1]=0x3f;\/\/\u969c\u788d\u3002\r\n\t}\r\n\tvis[sx][sy]=1;\r\n\tdfs(sx,sy);\r\n\tcout<<cnt;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 \u9a6c\u7684\u904d\u5386<\/h2>\n\n\n\n
\u662f\u597d\u9898\uff0c\u4e00\u9053\u7528bfs\u7684\u597d\u9898\u3002<\/p>\n\n\n\n
<\/p>\n\n\n\n
\n
\"\"<\/div><\/figure>\n<\/figure>\n\n\n\n
\u975e\u5e38\u611a\u7b28\u7684\u624b\u5199\u961f\u5217\u3002<\/p>\n\n\n\n
#include <iostream>\n#include <cstring>\n#include <algorithm>\nusing namespace std;\nconst int N=2e5;\nstruct note{\n\tint x;\/\/\u6a2a\u5750\u6807\u3002\n\tint y;\/\/\u7eb5\u5750\u6807\u3002\n\tint step;\/\/\u6b65\u6570\u3002\n};\nnote point[N];\nint movex[9]={0,2, 2, 1, 1,-1,-1,-2,-2};\nint movey[9]={0,1,-1, 2,-2, 2,-2, 1,-1};\nint world[405][405];\nint step[405][405];\nbool vis[405][405];\nint n,m;\nint mx,my;\nint main(){\n\tmemset(world,0x3f,sizeof(world));\/\/\n\tmemset(step,0,sizeof(step));\/\/\u7279\u5224\n\tcin>>n>>m;\/\/\u8f93\u5165N M\u3002\n\tcin>>mx>>my;\/\/\u8f93\u5165\u8d77\u70b9\u3002\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int l=1;l<=m;l++){\n\t\t\tworld[i][l]=1;\/\/\u80fd\u8d70\u7684\u70b9\u3002\n\t\t}\n\t}\n\t\/\/step\u524d+1 = step\u540e\u3002\n\tint head=1,tail=1;\n\tpoint[head].x = mx;\n\tpoint[head].y = my;\/\/\u8d77\u70b9\uff1f\uff1f\n\tvis[mx][my]=true;\n\ttail++;\n\twhile(head<tail){\n                        for(int i=1;i<=8;i++){\n\t\t\tint cur_x=point[head].x+movex[i];\/\/\u79fb\u52a8\u540e\u7684\u6a2a\u5750\u6807\u3002\n\t\t\tint cur_y=point[head].y+movey[i];\/\/\u79fb\u52a8\u540e\u7684\u7eb5\u5750\u6807\u3002\n\n\t\t\tif(cur_x<=0||cur_y<=0) continue;\/\/\u9632\u6b62\u6570\u7ec4\u8d8a\u754c\u3002\n\t\t\tif(world[cur_x][cur_y]==1&&vis[cur_x][cur_y]==false){\/\/\u53ef\u4ee5\u8d70 \u4e14 \u6ca1\u8d70\u8fc7\u3002\n\n\t\t\t\tpoint[tail].x=cur_x;\/\/\u8bb0\u5f55\u6a2a\u5750\u6807\u3002\n\t\t\t\tpoint[tail].y=cur_y;\/\/\u8bb0\u5f55\u7eb5\u5750\u6807\u3002\n\t\t\t\tvis[cur_x][cur_y]=true;\/\/\u8fd9\u4e2a\u70b9\u5df2\u7ecf\u8d70\u8fc7\u4e86\u3002\n\t\t\t\tstep[cur_x][cur_y]=step[point[head].x][point[head].y]+1;\/\/\u4ece\u5f00\u59cb\u904d\u5386\u516b\u4e2a\u65b9\u5411\u7684\u70b9\u7684STEP+1\u3002\n\t\t\t\ttail++;\/\/\u8bb0\u5f55 \u5165\u5217\u3002\n\/\/cout<<\"step head: \"<<step[point[head].x][point[head].y]<<endl;\n\/\/cout<<\"step cur : \"<<step[cur_x][cur_y]<<endl<<endl;\n\t\t\t}\n\t\t}\n\t\thead++;\/\/\u904d\u5386\u5b8c\u6210\u3002\n\t}\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int l=1;l<=m;l++){\n\t\t\tif(step[i][l]==0){\n\t\t\t\tstep[i][l]=-1;\/\/\u4ecd\u7136\u4e3a0\u7684\u70b9\u3002\n\t\t\t}\n\t\t}\n\t}\n\tstep[mx][my]=0;\/\/\u8d77\u70b9\u4e3a0\u3002\n\t\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int l=1;l<=m;l++){\n\t\t\tcout<<step[i][l]<<\"    \";\n\t\t}\n\t\tcout<<endl;\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u5f85\u7eed…………\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u641c\u7d22\u548c\u52a8\u6001\u89c4\u5212\u662f\u7b97\u6cd5\u754c\u7684\u4e24\u5ea7\u5927\u5c71\u3002 \u641c\u7d22\u672c\u8d28\u4e0a\u662f\u4e00\u79cd\u904d\u5386\uff0c\u662f\u5bf9\u6bcf\u4e00\u79cd\u60c5\u51b5\u64cd\u4f5c\u4e00\u904d\u3002 T1 \u8ff7\u5bab\uff08dfs\uff09 \u662f\u597d […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[3,11],"tags":[],"class_list":["post-94","post","type-post","status-publish","format-standard","hentry","category-3","category-11"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/94","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=94"}],"version-history":[{"count":1,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/94\/revisions"}],"predecessor-version":[{"id":97,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/94\/revisions\/97"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=94"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=94"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=94"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}