c + + anonymous school has opened many courses according to c + + programming.
It was a sunny day. The breeze caresses the earth, across the river bank and plays among the willows. Xiaohang left the dormitory and walked to the "algorithm classroom" in the spring shower.
The algorithm class is taught by XC teacher. "Ding - Ding -" the class bell rang, and GDN teacher walked into the classroom, "if you don't talk nonsense, class!"
Part I: understanding BFS
"Students have a good grasp of DFS, one of the basic algorithms. Today we will learn BFS, that is Width first search ! Please listen carefully! " GDN teacher scanned the students.
"BFS is a blind search method. Its purpose is to systematically expand and check all nodes in the graph to find the result. In other words, it does not consider the possible location of the result and thoroughly searches the whole graph until the result is found." GDN teacher looked at the students who listened carefully, "through the program you see now, we can realize its search process."
"Well, say, 'time is an important link to verify the truth' (I made it up). Let's do the problem now! Look at the problem."
Part II: doing questions
1. [width first search BFS] area
(File IO): input:area.in output:area.out
Time limit: 1000 ms • space limit: 262144 KB • specific limit
Title Description
Program to calculate the area of the following figures surrounded by "*". The area calculation method is to count the number of intersections of horizontal and vertical lines in the closed curve surrounded by * sign. As shown in the figure below, in the 10 * 10 two-dimensional array, there are "*" surrounding 15 points, so the area is 15.
input
Above
output
Above
sample input
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
sample output
15
include<cstdio>
using namespace std;
int n,m,a[15][15],b[15][15],de[1005][2],i,j=1,k;
int main()
{
freopen("area.in","r",stdin);
freopen("area.out","w",stdout);
for(int ii=1;ii<=10;ii++)
for(int jj=1;jj<=10;jj++)
{
scanf("%d",&a[ii][jj]);
if(a[ii][jj]==1)
k++;
}
if(k==0)
{
printf("100");
return 0;
}
de[1][1]=0;
de[1][2]=0;
b[0][0]=1;
a[0][0]=1;
k=0;
while(i<j)
{
i++;
for(int i1=-1;i1<=1;i1++)
{
if(i1==0)
continue;
if(de[i][1]+i1>=0&&de[i][1]+i1<=11&&a[de[i][1]+i1][de[i][2]]==0&&b[de[i][1]+i1][de[i][2]]==0)
{
j++;
de[j][1]=de[i][1]+i1;
de[j][2]=de[i][2];
a[de[j][1]][de[j][2]]=1;
b[de[j][1]][de[j][2]]=1;
}
}
for(int i1=-1;i1<=1;i1++)
{
if(i1==0)
continue;
if(de[i][2]+i1>=0&&de[i][2]+i1<=11&&a[de[i][1]][de[i][2]+i1]==0&&b[de[i][1]][de[i][2]+i1]==0)
{
j++;
de[j][1]=de[i][1];
de[j][2]=de[i][2]+i1;
a[de[j][1]][de[j][2]]=1;
b[de[j][1]][de[j][2]]=1;
}
}
}
for(int i1=1;i1<=10;i1++)
{
for(int j1=1;j1<=10;j1++)
{
if(a[i1][j1]==0)
k++;
}
}
printf("%d",k);
fclose(stdin);
fclose(stdout);
return 0;
}2. [width first search BFS] cells
(File IO): input:cell.in output:cell.out
Time limit: 1000 ms • space limit: 262144 KB • specific limit
Title Description
A rectangular array consists of numbers 0 to 9, and numbers 1 to 9 represent cells. Whether the cell is defined as up, down, left and right along the cell number or the cell number is the same cell, calculate the number of cells in a given rectangular array. For example:
Array:
4 10
0234500067
1034560500
2045600671
0000000089
e has 4 cells.
input
Such as title
output
Such as title
sample input
4 10 0234500067 1034560500 2045600671 0000000089
sample output
4
#include<bits/stdc++.h>
using namespace std;
struct zuobiao
{
int x,y;
};
queue<zuobiao>q;
zuobiao c;
int sum,n,m,fang[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char ma[105][105];
int visit[105][105];
void bfs(int x,int y)
{
sum++;
c.x=x;
c.y=y;
q.push(c);
visit[c.x][c.y]=1;
while(!q.empty())
{
zuobiao t=q.front(),ne;
q.pop();
for(int i=0;i<4;i++)
{
ne.x=t.x+fang[i][0];
ne.y=t.y+fang[i][1];
if(ne.x<=n&&ne.x>=1&&ne.y<=m&&ne.y>=1&&ma[ne.x][ne.y]!='0'&&visit[ne.x][ne.y]==0)
{
q.push(ne);
visit[ne.x][ne.y]=1;
}
}
}
}
int main()
{
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ma[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(visit[i][j]==0&&ma[i][j]!='0')
{
bfs(i,j);
}
}
}
cout<<sum;
fclose(stdin);
fclose(stdout);
} Part III: summary
"There is no specific approach to the problem of algorithm. We need to explore slowly, explore the law, practice more and do more, so as to really master it!" GDN teacher looked at the students with a serious face