同第一题,最短路径的板子题
这种题的一般思路:
广搜:
1.初始状态标记(初始元素入队,初始元素vis,ans,cnt等数据初始化)
2.进入while(!q.empty())
(1)取出队首元素放入now(不要忘记pop掉)
(2)枚举所有可能出现的可拓展情况(这里可以用for的临界来整活)
vis标记保证每个位点都只到达一次,这一次即为最短路径
(3)判断(边界,标记,题意)
3.输出ans即可
代码如下:
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 int n;int m; 9 char map[505][505]; 10 bool vis[505][505]; 11 int cnt=0; 12 struct note{ 13 int a;int b; 14 }; 15 queue<note>q; 16 int dx[5]={0,0,1,-1}; 17 int dy[5]={1,-1,0,0}; 18 19 bool bound(int nn,int mm) 20 { 21 if(nn>=1&&nn<=n&&mm>=1&&mm<=m) return 1; 22 else return 0; 23 } 24 25 void BFS(int x,int y) 26 { 27 note t;t.a=x;t.b=y; 28 q.push(t); 29 while(!q.empty()) 30 { 31 int nowx=q.front().a; 32 int nowy=q.front().b; 33 q.pop();//注意位置!!! 34 for(int i=0;i<4;i++) 35 { 36 int xx=nowx+dx[i]; 37 int yy=nowy+dy[i]; 38 if(bound(xx,yy)==1&&vis[xx][yy]==0&&map[xx][yy]!='0') 39 { 40 note k;k.a=xx;k.b=yy; 41 q.push(k); 42 vis[xx][yy]=1; 43 } 44 } 45 } 46 } 47 48 int main() 49 { 50 cin>>n>>m; 51 for(int i=1;i<=n;i++) 52 for(int j=1;j<=m;j++) 53 cin>>map[i][j]; 54 55 for(int i=1;i<=n;i++) 56 for(int j=1;j<=m;j++) 57 if(vis[i][j]==0&&map[i][j]!='0') 58 BFS(i,j),cnt++; 59 60 cout<<cnt; 61 62 return 0; 63 }
标签:include,nn,标记,int,vis,505,营救 From: https://www.cnblogs.com/xdzxxintong/p/16622980.html