= ，=  妈蛋，拓扑排序和欧拉回路先放一放，实在有点力不从心。先继续学习暴力破解法。在那之前，把八连块和走迷宫先记录一下。

八连块，此名字十分坑爹，其实只要是连着的黑色区域都叫做一个八连块。计算一个图中黑色八连快的个数，

分析：利用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<
    
     <
    

为了避免调用栈的溢出，不放选择用显式的栈来处理

stack
    
      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;//标志被访问过
     		//开始讲周围的8点压入栈 准备进行处理，每次处理时又会进行压入，所以这种方法其实还是效率蛮低的
     		//改良的话不放考虑一下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 
    
     #include 
     
      #include 
      
       #define M 1000using 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
       
         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
        
         =0&&ty
         
          0) { cout<
          
           >n>>m; for(int i=0;i
           
            >s; for(int j=0;j