1.深搜
深搜类似于树的先序遍历,通过每次访问一个点,无法继续搜索时进行回溯的思想解题
int n,m;//记录边界
int mov[4][2] = {1,0,-1,0,0,1,0,-1};
int vis[N][N],mapp[N][N];
int s = 0;//记录步数/时间
void DFS(int x,int y)
{
if(x = endx && y == endy)//条件判断
return ;
for(int i = 0; i<4; i++)//题意不一定是移动某个位置,可能就没办法循环,直接写搜索条件,满足条件就DFS();
{
int xx = x+mov[i][0];
int yy = y+mov[i][1];
if(xx>=n||xx<0||yy>=m||yy<0||vis[xx][yy])//判断是否越界
continue;
else
{
s++;//每搜一次加一
vis[xx][yy] = 1;
DFS(xx,yy);
//根据题意是否回溯
vis[xx][yy] = 0;
s--;
}
}
}
2.广搜
广搜和深搜不同,广搜思想是遍历每一个顶点时,依次遍历其所有的邻接点,然后再从这些邻接点出发,同样依次访问它们的邻接点。按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到
int m,n;
int mov[4][2] = {1,0,-1,0,0,1,0,-1};
int vis[N][N],mapp[N][N];
struct node
{
int x,y,step;
};
int BFS(int x,int y)//传入起点
{
//初始化条件
memset(vis,o,sizeof(vis));
queue<node>q; //广搜要用队列
node a,next;
a.x = x;
a.y = y;
a.step = 0;
vis[x][y] = 1;
q.push(a);
//搜索
while(!q.empty())
{
a = q.front();
q.pop();
if(mapp[a.x][a.y] == 'E')//结束条件
return a.step;
for(int i = 0; i<4; i++)
{
int xx = a.x+mov[i][0];
int yy = a.y+mov[i][1];
if(xx>=n||xx<0||yy>=m||yy<0||vis[xx][yy])//限制条件
continue;
else
{
next.x = xx;
next.y = yy;
next.step = a.step+1;
vis[xx][yy] = 1;
q.push(next);
}
}
}
return -1;//没有搜到/不满足条件
}
凌志编程机器人培训学校全体教师参加山东省青少年科···
由淄博市教体局,淄博市科协主办,凌志编程机器人培···
创客空间建设 能够给人们分享各种乐趣,通过电脑,···
在了解创客教育之前,我们首先了解下何为创客。创客···