深搜和广搜，深搜是一下走到头，广搜使用队列辅助实现。
例题做了一下，已过样例，没有评测机。
一个m*n的矩阵，问1有多少块，十字形范围内算同一块。
样例：
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
四块。
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int a[100][100]; bool pd[100][100]; int ans=0; //(-1,0),(1,0),(0,1),(0,-1) int x[4]={-1,1,0,0}; int y[4]={0,0,1,-1}; int m,n; void dfs(int h,int l) { pd[h][l]=1; for(int i=0;i<=3;i++) { int temp1=h+x[i]; int temp2=l+y[i]; if(temp1>=1 && temp1<=m && temp2>=1 && temp2<=n && pd[temp1][temp2]==0 && a[temp1][temp2]==1) dfs(temp1,temp2); } } int main() { scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); } memset(pd,0,sizeof(pd)); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(a[i][j]==1 && pd[i][j]==0) { dfs(i,j); ans++; } } } printf("%d",ans); return 0; }
分清深搜和广搜，地图的开xy数组用循环来走遍各个位置。flag用于判断是否走过，注意不要在dfs里面加计数器，在最外层加。
注意new和malloc都是对应的指针，普通的直接 int p或者node p啥的就行
广搜，一堆判定条件不要忘记了地图要是1
另外别忘了queue的头文件。还有他是front和back
#include<stdio.h> #include<iostream> #include<string.h> #include<queue> using namespace std; int a[100][100]; bool pd[100][100]; int ans=0; //(-1,0),(1,0),(0,1),(0,-1) int x[4]={-1,1,0,0}; int y[4]={0,0,1,-1}; int m,n; struct node{ int x,y; }; queue<node>q; void bfs(int h,int l) { ans++; node p; p.x=h; p.y=l; q.push(p); pd[h][l]=1; while(!q.empty()) { node temp=q.front(); q.pop(); for(int i=1;i<=4;i++) { int tempx=temp.x+x[i]; int tempy=temp.y+y[i]; if(tempx>=1 && tempx<=m && tempy>=1 && tempy<=n && pd[tempx][tempy]==0 && a[tempx][tempy]==1) { pd[tempx][tempy]=1; p.x=tempx; p.y=tempy; q.push(p); } } } } int main() { scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); } memset(pd,0,sizeof(pd)); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(a[i][j]==1 && pd[i][j]==0) { bfs(i,j); } } } printf("%d ",ans); return 0; }
书上地图那道题
注意最短数的计算过程中要在结构体里面定义，不然会出问题
#include<iostream> #include<stdio.h> #include<string.h> #include<queue> using namespace std; int a[100][100];// int pd[100][100]; int startx,starty,endx,endy; int ans=0; struct node{ int x,y; int step; }p; queue<node>q; //(0,1)(0,-1)(1,0)(-1,0) int x[4]={0,0,1,-1}; int y[4]={1,-1,0,0}; int bfs(int startx,int starty) { p.x=startx; p.y=starty; p.step=0; q.push(p); pd[startx][starty]=1; while(!q.empty()) { node temp=q.front(); q.pop(); ans++; int tempx,tempy; for(int i=0;i<=3;i++) { tempx=temp.x+x[i]; tempy=temp.y+y[i]; if(tempx==endx && tempy==endy) { return temp.step+1; } else if(a[tempx][tempy]==3 && pd[tempx][tempy]==0) { pd[tempx][tempy]=1; p.x=tempx; p.y=tempy; p.step=temp.step+1; q.push(p); } } } return -1; } int main() { int n,m; scanf("%d%d",&n,&m); getchar(); char temp; memset(a,0,sizeof(a)); memset(pd,0,sizeof(pd)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%c",&temp); if(temp=='S') { startx=i; starty=j; a[i][j]=1; } else if(temp=='T') { endx=i; endy=j; a[i][j]=2; } else if(temp=='.') a[i][j]=3; else a[i][j]=4; } getchar(); } printf("%d",bfs(startx,starty)); return 0; }