算法笔记-CPP

#图论

#深度优先搜索#DFS

#include
#include
using namespace std;
int n,m,t,sx,sy,ex,ey;
int a[10][10];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int ans=0;
void dfs(int x,int y){
	if(x==ex&&y==ey){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==0){
			a[nx][ny]=1;
			dfs(nx,ny);
			a[nx][ny]=0;
		}
	}
}
int main(){
	cin>>n>>m>>t>>sx>>sy>>ex>>ey;
	int tx,ty;
	while(t--){
		cin>>tx>>ty;
		a[tx][ty]=-1;//障碍 
	}
	a[sx][sy]=1;//已访问
	dfs(sx,sy);
	cout< 
BFS 
#BFS #广度优先搜索
 
★单源BFS 
BFS求的最短路径是指步数最少。
 
//节点结构
struct Node{
    int x,y;
    Node(int x,int y):x(x),y(y){}
    bool operator = (const Node&A)const{
        if(this->x==A.x&&this->y==A.y) return true;
        return false;
    }
};
//标记数组
bool visit[MAXW][MAXH]={false};
//记录路径
Node FatherNode[MAXW][MAXH];
Stack S;
//方向数组
int dir[4][2]={0,1,1,0,0,-1,-1,0};
bool BFS(Node &start,Node &end){
    queue Q;
    Node CurrentNode,AdjacentNode;
    int i;
    //将源点放进队列Q
    Q.push(Vs);
    visit[start.x][start.y]=true;
    while(!Q.empty()){
        //取出对头
        CurrentNode=Q.front();
        Q.pop();
        //判断相邻节点是不是end，是就结束函数，不是就推进队列Q并设置为已访问
        for(i=0;i<4;i++){
            AdjacentNode=Node(CurrentNode.x+dir[i][0],CurrentNode.y+dir[i][1]);
            if(AdjacentNode==end){
                FatherNode[AdjacentNode.x][AdjacentNode.y]=CurrentNode;
                return true;
            }
            if(IsValid(AdjacentNode)&&!visit[AdjacentNode.x][AdjacentNode.y]){
                Q.push(AdjacentNode);
                visit[AdjacentNode.x][AdjacentNode.y]=true;
                FatherNode[AdjacentNode.x][AdjacentNode.y]=CurrentNode;
            }
        }
    }
    return false;
}
//回溯FatherNode打印出最短路径
void Back(){
    Node t=FatherNode[4][4];
    while(!(t.x==0&&t.y==0)){
        S.push(t);
        t=FatherNode[t.x][t.y];
    }
}
 
 
多源BFS 
Acwing 173 矩阵距离
 
题目大意是求一01矩阵中每一点到矩阵中所有为1的位置的最短距离，输出这个“距离矩阵”。
 
假设一个虚拟节点，到结点值为1的距离为0。我们就由多源转成了单源问题。
 
#include 
#include 
#include 
typedef pair PII;
using namespace std;
const int N=1010;
int n,m;
char g[N][N];
int d[N][N];//到虚拟源点的最短距离
int dir[][2]={-1,0,0,-1,1,0,0,1};
void bfs(){
	memset(d,-1,sizeof d);
	queue q;
	for(int i=0;i
			if(g[i][j]=='1'){
				q.push({i,j});
				d[i][j]=0;
			}
		}
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		int x=t.first,y=t.second;
		for(int i=0;i<4;i++){
			int a=x+dir[i][0],b=y+dir[i][0];
			 if(a>=1&&a=1&&b
				 d[a][b]=d[x][y]+1;
				 q.push({a,b});
			 }
		}
	}
}
int main(){
	scnaf("%d",&n,&m);
	for(int i=0;i
		for(int j=0;j 
 
双向BFS 
双向广搜的步骤：
 
将开始结点和目标结点加入队列q
标记开始结点为1，目标结点为2
while(队列非空){
	从q.front()扩展出s个新结点
	如果 新扩展的结点被其他数字标记过
		那么 表示搜索的两端碰撞，搜索结束
	如果新的扩展结点是从开始结点扩展来的
		那么 将这s个结点标记为1，并且入队
	如果新的扩展结点是从目标结点扩展来的
		那么 将这s个结点标记为2，并且入队
}
 
BFS例题 
八数码问题
 
#include
#include
#include
#include
#include
#include