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;//没有搜到/不满足条件}
凌志编程机器人培训学校全体教师参加山东省青少年科···
由淄博市教体局,淄博市科协主办,凌志编程机器人培···
创客空间建设 能够给人们分享各种乐趣,通过电脑,···
在了解创客教育之前,我们首先了解下何为创客。创客···
