Peter算法小课堂—DFS

DFS

有的童鞋就问了：dfs明明前面讲过了，为啥还要讲捏？

洪水填充算法

Flood fill ,also called seed fill,is an algorithm that determines the area connected to a given node in the multi-demension array

解决方法

四方向

int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}

输入第x行y列的坐标，输出(x,y)的四个方向连通的坐标

#include <bits/stdc++.h>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int x,y;
int main(){
	cin>>x>>y;
	for(int k=0;k<4;k++){
		int nx=x+dx[k];int ny=y+dy[k];
		cout<<"("<<nx<<","<<ny<<")"<<endl;
	}
	return 0;
}

试试手

void dfs(int x,int y){
	d[x][y]='@';
	for(int k=0;k<8;k++){
		int nx=x+dx[k],ny=y+dy[k];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&d[nx][ny]=='-')
			dfs(nx,ny);
	}
}