= ，= 妈蛋，拓扑排序和欧拉回路先放一放，实在有点力不从心。先继续学习暴力破解法。在那之前，把八连块和走迷宫先记录一下。
八连块，此名字十分坑爹，其实只要是连着的黑色区域都叫做一个八连块。计算一个图中黑色八连快的个数，
分析：利用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;
}