= ,= 妈蛋,拓扑排序和欧拉回路先放一放,实在有点力不从心。先继续学习暴力破解法。在那之前,把八连块和走迷宫先记录一下。
八连块,此名字十分坑爹,其实只要是连着的黑色区域都叫做一个八连块。计算一个图中黑色八连快的个数,
分析:利用DFS的思想来从0,0起点遍历整个图,遍历的过程中先是寻找到一个没有被访问过的黑色点,然后对这个点开始分散地递归地分析其周围的连块,直到遇到边界。此时也使得这个区域的黑色点比标记过。
下面是我的垃圾代码。
char s[1000]; int map[1000][1000][2]; //最后两个数值[0] 是存储的黑白0是白色 1是黑色;[1] 是是否被访问过0是没访问过 1是访问过 //这是用了调用栈的方法来实现dfs的 ,但是这样做有可能造成溢出 void dfs(int x,int y) { if(map[x][y][0]==0||map[x][y][1]==1) return;//如果是白色或者被访问过就返回 map[x][y][1]=1;//自身被访问过 //否则开始递归访问周围的 dfs(x-1,y+1); dfs(x,y+1); dfs(x+1,y+1); dfs(x-1,y); dfs(x+1,y); dfs(x-1,y-1); dfs(x,y-1); dfs(x+1,y-1); } int main() { int n,cot=0; cin>>n; memset(map,0,sizeof(map)); //多维数组也可以这样清零 for(int i=1;i<=n;i++) { cin>>s; for(int j=1;j<=n;j++) map[i][j][0]=s[j-1]-'0'; //此处用到了一种创造白色边界的方法来便于控制出界 } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(map[i][j][0]==1&&map[i][j][1]==0) { cot++;//每次读到一个黑色点即可认为读到了一个黑色八连块 dfs(i,j);//开始在这个黑点周围释放毒气~ } } } cout<<cot<<endl; }
为了避免调用栈的溢出,不放选择用显式的栈来处理
stack<int> xs,ys; void dfs(int x,int y) { xs.push(x);ys.push(y);//首先将选中的黑色点压入栈底 while(!xs.empty()) { int xt=xs.top(); int yt=ys.top(); if(map[xt][yt][0]==0||map[xt][yt][1]==1) { xs.pop();ys.pop(); continue;} map[xt][yt][1]=1;//标志被访问过 <span style="white-space:pre"> </span>//开始讲周围的8点压入栈 准备进行处理,每次处理时又会进行压入,所以这种方法其实还是效率蛮低的 <span style="white-space:pre"> </span>//改良的话不放考虑一下xt,yt的范围 xs.push(xt-1);ys.push(yt-1); xs.push(xt-1);ys.push(yt); xs.push(xt-1);ys.push(yt+1); xs.push(xt);ys.push(yt-1); xs.push(xt);ys.push(yt+1); xs.push(xt+1);ys.push(yt-1); xs.push(xt+1);ys.push(yt); xs.push(xt+1);ys.push(yt+1); } }
这种时候发现递归其实并不一定适用于各种情况
下面研究一个最短路问题(貌似是叫这个名字)
走迷宫,寻找最短路线(其中一种就行,其实也只能找出来一种)
分析时,考虑怎么样才能得到最短路线。
1.把地图上每个点距离起点的最短距离写出来
2.把每个点的上一个来源找到(指的是实现起点到此点最短距离的路线)
下面是代码
其实我对BFS和DFS的理解还是不透彻,只是知道BFS用队列,DFS用栈(递归)
#include <stdio.h> #include <iostream> #include <queue> #define M 1000 using namespace std; int maze[M][M];//存储地图 1是空地 0是陷阱 char s[M];//存储临时输入变量 char name[]={' ','U','D','L','R'};//1 2 3 4 分别对应的走向 int n,m;//地图宽度n 地图高度m int dist[M][M],father[M][M];//dist 用来记录距离 father用来记录父节点 bool isvit[M][M]={false};//记录是否被走过,默认是false 没走过 int last_dir[M][M]; //下面两个数组非常简洁的解决了如何处理防线转换的判断问题 int dx[5]={0,0,0,-1,1}; int dy[5]={0,-1,1,0,0}; char path[M*M]; //bfs 用来遍历整个地图 同时进行标记每个点到起点的距离 //参数是起点的位置 0,0 void bfs(int x,int y) { queue<int> q; //用来存储即将要处理的节点,由于是bfs则用队列处理 int u =x+n*y;//记下起点编号 isvit[x][y]=true;//走过了 father[x][y]=u;//起点的父节点就是起点本身 dist[x][y]=0;//自己到自己是0 //开始遍历队列中的节点 q.push(u);//第一个要处理的就是起点 while(!q.empty()) { u=q.front();//记下即将要处理的节点编号 q.pop();//表示已经开始接受处理 int ux=u%n,uy=u/n; for(int i=1;i<=4;i++) { int tx=ux+dx[i]; int ty=uy+dy[i]; //tx ty 不越界且是空地 且没有被访问过 if(tx>=0&&tx<n&&ty>=0&&ty<m&&maze[tx][ty]&&!isvit[tx][ty]) { dist[tx][ty]=dist[ux][uy]+1;//起点到此扩展节点的距离就是起点到其父节点最短距离+1 father[tx][ty]=u;//记录父节点 isvit[tx][ty]=true;//标志被访问过 last_dir[tx][ty]=i; int v=tx+ty*n; q.push(v); } } } } //打印路线图 递归调用 向上一个节点靠近 反向输出 void print_path(int x,int y) { int fa=father[x][y]; if(x==0&&y==0) return; //因为路线过程中只有起点的父节点是0,0需要直接退回 int tx=fa%n; int ty=fa/n; print_path(tx,ty);//起点的父节点是0,0 所以会退回 其他的点都有父节点 cout<<name[last_dir[x][y]]; } //不用递归来做防止栈越界 void print_path2(int x,int y) { int i=0; while(!(x==0&&y==0)) { int fa=father[x][y]; int tx=fa%n; int ty=fa/n; path[i++]=name[last_dir[x][y]]; x=tx;y=ty;//此处相当于更新了队首元素 } //此时i比下标上限大1 while(i>0) { cout<<path[--i]; } } int main() { freopen("in47.txt","r",stdin); freopen("out47.txt","w",stdout); cin>>n>>m; for(int i=0;i<m;i++) { cin>>s; for(int j=0;j<n;j++) maze[j][i]=s[j]-'0'; } bfs(0,0); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) cout<<dist[j][i]<<"\t"; cout<<endl; } cout<<endl; cout<<endl; cout<<endl; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) cout<<father[j][i]<<"\t"; cout<<endl; } cout<<endl; cout<<endl; cout<<endl; print_path(4,0); cout<<endl; print_path2(4,0); return 0; }