{"id":344,"date":"2024-03-30T08:41:33","date_gmt":"2024-03-30T00:41:33","guid":{"rendered":"https:\/\/www.sxr666.cn\/?p=344"},"modified":"2024-03-30T09:28:19","modified_gmt":"2024-03-30T01:28:19","slug":"bfs%ef%bc%88%e5%b9%bf%e5%ba%a6%e4%bc%98%e5%85%88%e6%90%9c%e7%b4%a2%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.sxr666.cn\/index.php\/2024\/03\/30\/bfs%ef%bc%88%e5%b9%bf%e5%ba%a6%e4%bc%98%e5%85%88%e6%90%9c%e7%b4%a2%ef%bc%89\/","title":{"rendered":"BFS\uff08\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff09"},"content":{"rendered":"\n

\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff08\u6216\u79f0\u5bbd\u5ea6\u4f18\u5148\u641c\u7d22)\uff1a\u4e00\u822c\u7528\u961f\u5217(queue)\u8fd9\u79cd\u4f60\u6570\u636e\u7ed3\u6784\u6765\u5177\u4f53\u5b9e\u73b0BFS\uff0c\u751a\u81f3\u53ef\u4ee5\u8bf4\u201cBFS=\u961f\u5217\u201d\u3002<\/p>\n\n\n\n

\u4e00\u3001Red and Black<\/a><\/p>\n\n\n\n

#include <iostream>\r\n#include <queue>\r\nusing namespace std;\r\nchar room[23][23];\r\nint dir[4][2]={\r\n\t{-1,0},\r\n\t{1,0},\r\n\t{0,-1},\r\n\t{0,1}\r\n};\r\nint Wx,Hy,num;\r\n#define CHECK(x,y) (x<Wx&&x>=0&&y<Hy&&y>=0)\r\nstruct node {int x,y;};\r\n\r\nvoid BFS(int dx,int dy)\r\n{\r\n\tnum=1;\r\n\tqueue <node> q;\r\n\tnode start,next;\r\n\tstart.x=dx;\r\n\tstart.y=dy;\r\n\tq.push(start);\r\n\twhile(!q.empty()){\r\n\t\tstart=q.front();\r\n\t\tq.pop();\r\n\t\tfor(int i=0;i<4;i++){\r\n\t\t\tnext.x=start.x+dir[i][0];\r\n\t\t\tnext.y=start.y+dir[i][1];\r\n\t\t\tif(CHECK(next.x,next.y)&&room[next.x][next.y]=='.'){\r\n\t\t\t\troom[next.x][next.y]='#';\r\n\t\t\t\tnum++;\r\n\t\t\t\tq.push(next);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}\r\n\r\nint main(){\r\n\tint x,y,dx,dy;\r\n\twhile(cin>>Wx>>Hy){\r\n\t\tif(Wx==0&&Hy==0) break;\r\n\t\tfor(y=0;y<Hy;y++){\r\n\t\t\tfor(x=0;x<Wx;x++){\r\n\t\t\t\tcin>>room[x][y];\r\n\t\t\t\tif(room[x][y]=='@'){\r\n\t\t\t\t\tdx=x;\r\n\t\t\t\t\tdy=y;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tnum=0;\r\n\t\tBFS(dx,dy);\r\n\t\tcout<<num<<endl;\r\n\t}\t\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n\n\n\n
\u4e8c\u3001\u8ff7\u5bab\u5bfb\u8def<\/a><\/p>\n\n\n\n
#include <iostream>\r\n#include <queue>\r\nusing namespace std;\r\n\r\nchar room[100][100];\r\nint dir[4][2]={\r\n\t{-1,0},\r\n\t{1,0},\r\n\t{0,-1},\r\n\t{0,1}\r\n};\r\n\r\n#define CHECK(x,y) (x<=n&&x>0&&y<=m&&y>0)\r\nstruct node{int x,y;};\r\n\r\nint BFS(int n,int m){\r\n\tint flag=0;\r\n\troom[1][1]='#';\r\n\tqueue <node> q;\r\n\tnode start,next;\r\n\tstart.x=1;\r\n\tstart.y=1;\r\n\tq.push(start);\r\n\twhile(!q.empty()){\r\n\t\tstart=q.front();\r\n\t\tq.pop();\r\n\t\tfor(int i=0;i<4;i++){\r\n\t\t\tnext.x=start.x+dir[i][0];\r\n\t\t\tnext.y=start.y+dir[i][1];\r\n\t\t\tif(CHECK(next.x,next.y)&&room[next.x][next.y]=='.'){\r\n\t\t\t\troom[next.x][next.y]='#';\r\n\t\t\t\tif(next.x==n&&next.y==m) flag++;\r\n\t\t\t\tq.push(next);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\treturn flag;\r\n}\r\n\r\nint main(){\r\n\tint x,y,n,m;\r\n\twhile(cin>>n>>m){\r\n\t\t\r\n\t\tif(n==0&&m==0) break;\r\n\t\tfor(x=1;x<=n;x++){\r\n\t\t\tfor(y=1;y<=m;y++){\r\n\t\t\t\tcin>>room[x][y];\r\n\t\t\t}\r\n\t\t}\r\n\t\tif(BFS(n,m)) cout<<\"Yes\";\r\n\t\telse cout<<\"No\";\r\n\t}\r\n}\n<\/code><\/pre>\n\n\n\n
\u4e09\u3001\u586b\u6d82\u989c\u8272<\/a><\/p>\n\n\n\n
#include <bits\/stdc++.h>\r\nusing namespace std;\r\nint room[35][35];\r\nint bigroom[35][35];\r\nint hhh[35][35];\r\nint dir[4][2]={\r\n\t{-1,0},\r\n\t{1,0},\r\n\t{0,-1},\r\n\t{0,1}\r\n};\r\nint n;\r\n\r\n#define CHECK(x,y) (x>=1&&x<=n&&y>=1&&y<=n)\r\n#define CHECKPRO(x,y) (x==1||x==n||y==1||y==n)\r\nstruct node{int x,y;};\r\n\r\nvoid BFS(int k,int l){\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int j=1;j<=n;j++){\r\n\t\t\troom[i][j]=bigroom[i][j];\r\n\t\t}\r\n\t}\r\n\tint flag=0;\r\n\tqueue <node> q;\r\n\tnode start,next;\r\n\tstart.x=k;\r\n\tstart.y=l;\r\n\troom[k][l]=3;\r\n\tq.push(start);\r\n\twhile(!q.empty()){\r\n\t\tstart=q.front();\r\n\t\tq.pop();\r\n\t\tfor(int i=0;i<4;i++){\r\n\t\t\tnext.x=start.x+dir[i][0];\r\n\t\t\tnext.y=start.y+dir[i][1];\r\n\t\t\tif(CHECK(next.x,next.y)&&room[next.x][next.y]==0){\r\n\t\t\t\troom[next.x][next.y]=3;\r\n\t\t\t\tq.push(next);\r\n\t\t\t\t\r\n\t\t\t\t\/\/cout<<next.x<<\"     \"<<next.y<<endl;\r\n\t\t\t\t\r\n\t\t\t\tif(CHECKPRO(next.x,next.y)) flag++;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tif(!flag&&bigroom[k][l]==0) hhh[k][l]=1;\r\n\treturn;\r\n}\r\n\r\n\r\nint main(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int j=1;j<=n;j++){\r\n\t\t\tcin>>bigroom[i][j];\r\n\t\t}\r\n\t}\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int j=1;j<=n;j++){\r\n\t\t\tBFS(i,j);\r\n\t\t}\r\n\t}\t\r\n\t\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int j=1;j<=n;j++){\r\n\t\t\t\/\/BFS(i,j);\r\n\t\t\tif(hhh[i][j]==1&&!(bigroom[i][j]==0&&CHECKPRO(i,j))) bigroom[i][j]=2;\r\n\t\t\t\/\/if(bigroom[i][j]==0&&CHECKPRO(i,j)) bigroom[i][j]=0;\r\n\t\t\tcout<<bigroom[i][j]<<\" \";\r\n\t\t}\r\n\t\tcout<<endl;\r\n\t}\r\n\treturn 0;\r\n}\n\r<\/code><\/pre>\n\n\n\n
\u56db\u3001\u00a0[USACO10OCT] Lake Counting S<\/a><\/p>\n\n\n\n
#include <bits\/stdc++.h>\r\nusing namespace std;\r\nchar room[120][120];\r\nint dir[8][2]={\r\n\t{-1,-1},\r\n\t{-1,0},\r\n\t{-1,1},\r\n\t{0,-1},\r\n\t{0,1},\r\n\t{1,-1},\r\n\t{1,0},\r\n\t{1,1}\r\n};\r\nint wx,hy,num=0;\r\n\r\n#define CHECK(x,y) (x>=1&&x<=wx&&y>=1&&y<=hy)\r\nstruct node {int x,y;};\r\n\r\nint BFS(int dx,int dy){\r\n\tint flag=0;\r\n\tqueue <node> q;\r\n\tnode start,next;\r\n\tstart.x=dx;\r\n\tstart.y=dy;\r\n\troom[dx][dy]='.';\r\n\tq.push(start);\r\n\twhile(!q.empty()){\r\n\t\tflag++;\r\n\t\tstart=q.front();\r\n\t\tq.pop();\r\n\t\tfor(int i=0;i<8;i++){\r\n\t\t\tnext.x=start.x+dir[i][0];\r\n\t\t\tnext.y=start.y+dir[i][1];\r\n\t\t\tif(CHECK(next.x,next.y)&&room[next.x][next.y]=='W'){\r\n\t\t\t\tq.push(next);\r\n\t\t\t\troom[next.x][next.y]='.';\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\treturn flag;\r\n}\r\n\r\n\r\nint main(){\r\n\tcin>>wx>>hy;\r\n\tint tem,num=0;\r\n\tfor(int i=1;i<=wx;i++){\r\n\t\tfor(int j=1;j<=hy;j++){\r\n\t\t\tcin>>room[i][j];\r\n\t\t}\r\n\t}\r\n\tfor(int i=1;i<=wx;i++){\r\n\t\tfor(int j=1;j<=hy;j++){\r\n\t\t\tif(room[i][j]=='W'){\r\n\t\t\t\tBFS(i,j);\r\n\t\t\t\tnum++;\r\n\t\t\t}\r\n\t\t}\r\n\t}\t\r\n\tcout<<num;\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff08\u6216\u79f0\u5bbd\u5ea6\u4f18\u5148\u641c\u7d22)\uff1a\u4e00\u822c\u7528\u961f\u5217(qu …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[26],"tags":[23,25],"_links":{"self":[{"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/posts\/344"}],"collection":[{"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/comments?post=344"}],"version-history":[{"count":3,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/posts\/344\/revisions"}],"predecessor-version":[{"id":350,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/posts\/344\/revisions\/350"}],"wp:attachment":[{"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/media?parent=344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/categories?post=344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sxr666.cn\/index.php\/wp-json\/wp\/v2\/tags?post=344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}