搜索算法刷题总结(DFS+BFS)

简介: 本文总结了DFS和BFS算法的基本模板及其典型应用。DFS部分包括指数型枚举、排列组合、N皇后问题等经典案例,展示了如何通过递归实现深度优先搜索。BFS部分涵盖了迷宫问题、马的遍历、洪水灌溉等场景,演示了使用队列实现广度优先搜索的方法。每种算法都提供了C++和Java的双语代码实现,包含状态标记、路径记录等关键步骤。文章还涉及剪枝优化、多源BFS等进阶技巧,为理解这两种基础搜索算法提供了全面参考。

 1.DFS

1.1 DFS基本模板

指数型枚举

https://www.acwing.com/problem/content/94/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=17;
int n;
bool status[N];
void dfs(int x){
  if(x==n+1){
    for(int i=1;i<=n;i++){
      if(status[i]) cout<<i<<" ";
    }
    cout<<endl;
    return;
  }
  status[x]=true;
  dfs(x+1);
  status[x]=false;
  dfs(x+1); 
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  dfs(1);
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=17;
    public static int n;
    public static boolean[] status=new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        dfs(1);
        
    }
    
    public static void dfs(int x){
        if(x==n+1){
            for(int i=1;i<=n;i++){
                if(status[i]) System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
        status[x]=true;
        dfs(x+1);
        status[x]=false;
        dfs(x+1);
    }
    
}

image.gif

排列数字

https://www.acwing.com/problem/content/844/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int arr[N];
bool status[N];
int n;
void dfs(int x){
  if(x==n+1){
    for(int i=1;i<=n;i++){
      cout<<arr[i]<<" ";
    }
    cout<<endl;
    return;
  }
  
  for(int i=1;i<=n;i++){
    if(!status[i]){
      arr[x]=i;
      status[i]=true;
      dfs(x+1);
      arr[x]=0;
      status[i]=false;
    }
  }
  
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  dfs(1);
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=10;
    public static int n;
    public static int[] arr=new int[N];
    public static boolean[] status=new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        dfs(1);
    }
    
    public static void dfs(int x){
        if(x==n+1){
            for(int i=1;i<=n;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }
        for(int i=1;i<=n;i++){
            if(!status[i]){
                arr[x]=i;
                status[i]=true;
                dfs(x+1);
                arr[x]=0;
                status[i]=false;
            }
        }
        
    }
 
}

image.gif

组合数

https://www.luogu.com.cn/problem/P1157

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=24;
int n,r;
int arr[N];
void dfs(int x,int start){
  if(x==r+1){
    for(int i=1;i<=r;i++){
      printf("%3d",arr[i]);
    }
    cout<<endl;
    return;
  }
  for(int i=start;i<=n;i++){
    arr[x]=i;
    dfs(x+1,i+1);
    arr[x]=0;
  }
}
int main()
{
  scanf("%d%d",&n,&r);
  dfs(1,1);
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=24;
    public static int n,r;
    public static int[] arr=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        r=sc.nextInt();
        dfs(1,1);
    }
    public static void dfs(int x,int start){
        if(x==r+1){
            for(int i=1;i<=r;i++){
                System.out.printf("%3d",arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start;i<=n;i++){
            arr[x]=i;
            dfs(x+1,i+1);
            arr[x]=0;
        }
    }
}

image.gif

1.2 DFS习题

N皇后问题

https://www.acwing.com/problem/content/845/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int n;
char graph[N][N];
bool col[N];
bool zuo[2*N+10];
bool you[2*N+10];
void dfs(int x){
  if(x==n){
    for(int i=0;i<n;i++){
      cout<<graph[i]<<endl;
    }
    cout<<endl;
    return;
  }
    
  for(int i=0;i<n;i++){
    if(!col[i] && !zuo[x+i] && !you[x-i+n]){
      graph[x][i]='Q'; 
      col[i]=zuo[x+i]=you[x-i+n]=true;
      dfs(x+1);
      col[i]=zuo[x+i]=you[x-i+n]=false;
      graph[x][i]='.';
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      graph[i][j]='.';
    }
  }
  dfs(0);
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=12;
    public static int n;
    public static char[][] graph=new char[N][N];
    public static boolean[]col=new boolean[N];
    public static boolean[]zuo=new boolean[2*N+1];
    public static boolean[]you=new boolean[2*N+1];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                graph[i][j]='.';
            }
        }
        dfs(0);
    }
    public static void dfs(int x){
        if(x==n){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(graph[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for(int i=0;i<n;i++){
            if(!col[i] && !zuo[x+i] && !you[x-i+n]){
                graph[x][i]='Q';
                col[i]=zuo[x+i]=you[x-i+n]=true;
                dfs(x+1);
                col[i]=zuo[x+i]=you[x-i+n]=false;
                graph[x][i]='.';
            }
        }
    }
}

image.gif

棋盘问题

https://www.acwing.com/problem/content/1116/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n,k;
char graph[N][N];
bool col[N];
int res;
void dfs(int x,int sum){
  if(sum==k){
    res++;
    return;
  }
  if(x==n) return;
  for(int i=0;i<n;i++){
    if(!col[i] && graph[x][i]=='#'){
      col[i]=true;
      dfs(x+1,sum+1);
      col[i]=false;
    }
  }
  
  dfs(x+1,sum);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  while(cin>>n>>k){
    if(n==-1 && k==-1) break;
    res=0;
    memset(col,false,sizeof(col));
    for(int i=0;i<n;i++){
      cin>>graph[i];
    }
    dfs(0,0);
    cout<<res<<endl;
  }
  
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=10;
    public static int n,k;
    public static char[][]graph=new char[N][N];
    public static boolean[] status=new boolean[N];
    public static int res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while((n=sc.nextInt())!=-1 && (k=sc.nextInt())!=-1){
            res=0;
            Arrays.fill(status,false);
            for(int i=0;i<n;i++){
                String s=sc.next();
                for(int j=0;j<n;j++){
                    graph[i][j]=s.charAt(j);
                }
            }
            dfs(0,0);
            System.out.println(res);
        }
    }
    public static void dfs(int x,int sum){
        if(sum==k){
            res++;
            return;
        }
        if(x==n) return;
        for(int i=0;i<n;i++){
            if(!status[i] && graph[x][i]=='#'){
                status[i]=true;
                dfs(x+1,sum+1);
                status[i]=false;
            }
        }
        dfs(x+1,sum);
    }
}

image.gif

选数

https://www.luogu.com.cn/problem/P1036

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,k;
int arr[N];
int brr[N];
int res;
bool isPrime(int x){
  for(int i=2;i*i<=x;i++){
    if(x%i==0) return false;
  }
  return true;
}
void dfs(int x,int start){
  if(x==k+1){
    int sum=0;
    for(int i=1;i<=k;i++) sum+=brr[i];
    if(isPrime(sum)) res++;
    return;
  }
  
  for(int i=start;i<=n;i++){
    brr[x]=arr[i];
    dfs(x+1,i+1);
    brr[x]=0;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>arr[i];
  dfs(1,1);
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=25;
    public static int n,k,res;
    public static int[]arr=new int[N];
    public static int[]brr=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        for(int i=1;i<=n;i++) arr[i]=sc.nextInt();
        dfs(1,1);
        System.out.println(res);
    }
    public static void dfs(int x,int start){
        if(x==k+1){
            int sum=0;
            for(int i=1;i<=k;i++) sum+=brr[i];
            if(isPrime(sum)) res++;
            return;
        }
        for(int i=start;i<=n;i++){
            brr[x]=arr[i];
            dfs(x+1,i+1);
            brr[x]=0;
        }
    }
    public static boolean isPrime(int x){
        for(int i=2;i*i<=x;i++){
            if(x%i==0) return false;
        }
        return true;
    }
}

image.gif

烧鸡

https://www.luogu.com.cn/problem/P2089

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=11;
const int M=1e5+10;
int n;
int arr[N];
int cnt;
int res[M][N];
void dfs(int x){
  if(x==11){
    int sum=0;
    for(int i=1;i<=10;i++){
      sum+=arr[i];
    }
    if(sum==n){
      cnt++;
      for(int i=1;i<=10;i++){
        res[cnt][i]=arr[i];
      }
      return;
    }
    return;
  }
  
  for(int i=1;i<=3;i++){
    arr[x]=i;
    dfs(x+1);
    arr[x]=0;
  }
  
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  dfs(1);
  cout<<cnt<<endl;
  for(int i=1;i<=cnt;i++){
    for(int j=1;j<=10;j++){
      cout<<res[i][j]<<" ";
    }
    cout<<endl;
  } 
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=11;
    public static final int M= (int) (1e5+10);
    public static int n;
    public static int[]arr=new int[N];
    public static int cnt;
    public static int [][]res=new int[M][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        dfs(1);
        System.out.println(cnt);
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=10;j++){
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void dfs(int x){
        if(x==11){
            int sum=0;
            for(int i=1;i<=10;i++) sum+=arr[i];
            if(sum==n){
                cnt++;
                for(int i=1;i<=10;i++) res[cnt][i]=arr[i];
                return;
            }
            return;
        }
        for(int i=1;i<=3;i++){
            arr[x]=i;
            dfs(x+1);
            arr[x]=0;
        }
    }
}

image.gif

PERKENT

https://www.luogu.com.cn/problem/P2036

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
const int N=15;
int n;
int s[N],b[N];
bool status[N];
int res=MAX;
void dfs(int x){
  if(x==n+1){
    int sum1=1,sum2=0;
    bool flag=false;
    for(int i=1;i<=n;i++){
      if(status[i]){
        sum1*=s[i];
        sum2+=b[i];
        flag=true;
      }
    }
    if(flag) res=min(res,abs(sum1-sum2));
    return;
  }
  
  status[x]=true;
  dfs(x+1);
  status[x]=false;
  dfs(x+1);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>s[i]>>b[i];
  }
  dfs(1);
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=15;
    public static final int MAX=0x3f3f3f3f;
    public static int n;
    public static int []s=new int[N];
    public static int []b=new int[N];
    public static boolean []status=new boolean[N];
    public static int res=MAX;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            s[i]=sc.nextInt();
            b[i]=sc.nextInt();
        }
        dfs(1);
        System.out.println(res);
    }
    public static void dfs(int x){
        if(x==n+1){
            int sum1=1,sum2=0;
            boolean flag=false;
            for(int i=1;i<=n;i++){
                if(status[i]){
                    sum1*=s[i];
                    sum2+=b[i];
                    flag=true;
                }
            }
            if(flag){
                res=Math.min(res,Math.abs(sum2-sum1));
            }
            return;
        }
        status[x]=true;
        dfs(x+1);
        status[x]=false;
        dfs(x+1);
    }
}

image.gif

火星人

https://www.luogu.com.cn/problem/P1088

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int arr[N];
int brr[N];
bool status[N];
int cnt;
bool flag;
void dfs(int x){
  if(flag) return;
  if(x==n+1){
    cnt++;
    if(cnt==m+1){
      flag=true;
      for(int i=1;i<=n;i++){
        cout<<brr[i]<<" ";
      }
      return;
    }
  }
  
  for(int i=1;i<=n;i++){
    if(cnt==0) i=arr[x];
    if(!status[i]){
      brr[x]=i;
      status[i]=true;
      dfs(x+1);
      brr[x]=0;
      status[i]=false;
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
  }
  
  dfs(1);
  
  
  return 0;
}

image.gif

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int arr[N]; // 存储排列,1基/0基均可,此处用0基适配STL
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 循环m次,求第m个后继排列
    for (int i = 0; i < m; i++) {
        // STL内置next_permutation:直接对数组进行修改,返回是否存在下一个排列
        // 题目保证结果不超出范围,因此无需判断返回值
        next_permutation(arr, arr + n);
    }
    for (int i = 0; i < n; i++) {
        cout<<arr[i]<<" "; 
    }
    return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,m;
    public static int cnt;
    public static boolean flag;
    public static int []arr=new int[N];
    public static int []brr=new int[N];
    public static boolean[] status=new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++) arr[i]=sc.nextInt();
        dfs(1);
    }
    public static void dfs(int x){
        if(flag) return;
        if(x==n+1){
            cnt++;
            if(cnt==m+1){
                flag=true;
                for(int i=1;i<=n;i++){
                    System.out.print(brr[i]+" ");
                }
                return;
            }
            return;
        }
        for(int i=1;i<=n;i++){
            if(cnt==0) i=arr[x];
            if(!status[i]){
                brr[x]=i;
                status[i]=true;
                dfs(x+1);
                status[i]=false;
                brr[x]=0;
            }
        }
    }
}

image.gif

火柴棒等式

https://www.luogu.com.cn/problem/P1149

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int mode[N];
int n;
int arr[5];
int res;
void dfs(int x,int sum){
  if(sum>n) return;
  if(x==4){
    if(arr[1]+arr[2]==arr[3] && sum==n){
      res++;  
    }
    return;
  }
  
  for(int i=0;i<=1000;i++){
    arr[x]=i;
    dfs(x+1,sum+mode[i]);
    arr[x]=0;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  mode[0]=6;
  mode[1]=2;
  mode[2]=5;
  mode[3]=5;
  mode[4]=4;
  mode[5]=5;
  mode[6]=6;
  mode[7]=3;
  mode[8]=7;
  mode[9]=6;
  cin>>n;
  n-=4;
  for(int i=10;i<=1000;i++){
    mode[i]=mode[i/10]+mode[i%10];
  }
  dfs(1,0); 
  cout<<res<<endl;
  
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n;
    public static int []mode=new int[N];
    public static int[] arr=new int[5];
    public static int res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        n-=4;
        mode[0]=6;
        mode[1]=2;
        mode[2]=5;
        mode[3]=5;
        mode[4]=4;
        mode[5]=5;
        mode[6]=6;
        mode[7]=3;
        mode[8]=7;
        mode[9]=6;
        for(int i=10;i<=1000;i++){
            mode[i]=mode[i/10]+mode[i%10];
        }
        dfs(1,0);
        System.out.println(res);
    }
    public static void dfs(int x,int sum){
        if(sum>n) return;
        if(x==4){
            if(arr[1]+arr[2]==arr[3] && sum==n){
                res++;
            }
            return;
        }
        for(int i=0;i<=1000;i++){
            arr[x]=i;
            dfs(x+1,sum+mode[i]);
            arr[x]=0;
        }
    }
}

image.gif

数的划分

https://www.luogu.com.cn/problem/P1025

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=220;
int n,k;
int arr[N];
int res;
void dfs(int x,int start,int sum){
  if(x==k+1){
    if(sum==n){
      res++;
    }
    return;
  }
  for(int i=start;i+sum<=n;i++){
    arr[x]=i;
    dfs(x+1,i,sum+i);
    arr[x]=0;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>k;
  dfs(1,1,0);
  cout<<res<<endl;
    
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static final int N=220;
    public static int n,k;
    public static int[]arr=new int[N];
    public static int res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        dfs(1,1,0);
        System.out.println(res);
    }
    public static void dfs(int x,int start,int sum){
        if(x==k+1){
            if(sum==n){
                res++;
            }
            return;
        }
        for(int i=start;i+sum<=n;i++){
            arr[x]=i;
            dfs(x+1,i,sum+i);
            arr[x]=0;
        }
    }
}

image.gif

2.BFS

1.1 BFS基本模板

入门

https://www.luogu.com.cn/problem/P1683

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII; 
const int N=25;
int w,h;
char graph[N][N];
bool status[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int res=1;
void bfs(int x,int y){
  queue<PII> q;
  q.push({x,y});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<4;i++){
      x=t.first+dx[i];
      y=t.second+dy[i];
      if(x>=0 & x<h && y>=0 && y<w
      && !status[x][y] && graph[x][y]=='.'){
        status[x][y]=true;
        res++;
        q.push({x,y}); 
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>w>>h;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>graph[i][j];
    }
  }
  
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(graph[i][j]=='@'){
        bfs(i,j);
      }
    }
  }
  cout<<res<<endl;    
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=25;
    public static int w,h;
    public static char[][] graph=new char[N][N];
    public static boolean[][] status=new boolean[N][N];
    public static int res=1;
    public static int dx[]={0,0,1,-1};
    public static int dy[]={1,-1,0,0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w=sc.nextInt();
        h=sc.nextInt();
        for(int i=0;i<h;i++){
            String s=sc.next();
            for(int j=0;j<w;j++){
                graph[i][j]=s.charAt(j);
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(graph[i][j]=='@'){
                    bfs(i,j);
                }
            }
        }
        System.out.println(res);
    }
    public static void bfs(int x,int y){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        while(!q.isEmpty()){
            Node node=q.poll();
            for(int i=0;i<4;i++){
                x=node.x+dx[i];
                y=node.y+dy[i];
                if(x>=0 && x<h && y>=0 && y<w && !status[x][y] && graph[x][y]=='.'){
                    res++;
                    status[x][y]=true;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

走迷宫

https://www.acwing.com/problem/content/846/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int graph[N][N];
int dist[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs(){
  queue<PII> q;
  q.push({0,0});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<4;i++){
      int x=t.first+dx[i];
      int y=t.second+dy[i];
      if(x>=0 && x<n & y>=0 && y<m
      && dist[x][y]==-1 && graph[x][y]==0){
        dist[x][y]=dist[t.first][t.second]+1;
        q.push({x,y});
      }
    }
  } 
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>graph[i][j];
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      dist[i][j]=-1;
    }
  }
  dist[0][0]=0;
  bfs();  
  cout<<dist[n-1][m-1];
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=110;
    public static int n,m;
    public static int[][]graph=new int[N][N];
    public static int[][]dist=new int[N][N];
    public static int dx[]={0,0,1,-1};
    public static int dy[]={1,-1,0,0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j]=sc.nextInt();
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dist[i][j]=-1;
            }
        }
        dist[0][0]=0;
        bfs();
        System.out.println(dist[n-1][m-1]);
    }
    public static void bfs(){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(0,0));
        while (!q.isEmpty()){
            Node node=q.poll();
            for (int i = 0; i < 4; i++) {
                int x=node.x+dx[i];
                int y=node.y+dy[i];
                if(x>=0 && x<n && y>=0 && y<m
                && graph[x][y]==0 && dist[x][y]==-1){
                    dist[x][y]=dist[node.x][node.y]+1;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

洪水灌溉

https://www.luogu.com.cn/problem/P1596

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
char graph[N][N];
bool status[N][N];
int dx[8]={1,1,0,0,-1,-1,1,-1};
int dy[8]={1,-1,1,-1,1,-1,0,0};
int res;
void bfs(int x,int y){
  queue<PII> q;
  q.push({x,y});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<8;i++){
      x=t.first+dx[i];
      y=t.second+dy[i];
      if(x>=0 && x<n && y>=0 && y<m
      && !status[x][y] && graph[x][y]=='W'){
        status[x][y]=true;
        q.push({x,y});
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>graph[i][j];
    }
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(graph[i][j]=='W' && !status[i][j]){
        status[i][j]=true;
        res++;
        bfs(i,j);
      }
    }
  }
  cout<<res<<endl;  
  
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=110;
    public static int n,m,res;
    public static char[][] graph=new char[N][N];
    public static boolean[][] status=new boolean[N][N];
    public static int dx[]={0,0,1,-1,1,1,-1,-1};
    public static int dy[]={1,-1,0,0,-1,1,-1,1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 0; i < n; i++) {
            String s=sc.next();
            for (int j = 0; j < m; j++) {
                graph[i][j]=s.charAt(j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(graph[i][j]=='W' && !status[i][j]){
                    bfs(i,j);
                    res++;
                }
            }
        }
        System.out.println(res);
    }
    public static void bfs(int x,int y){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        while (!q.isEmpty()){
            Node node = q.poll();
            for (int i = 0; i < 8; i++) {
                x=node.x+dx[i];
                y= node.y+dy[i];
                if(x>=0 && x<n && y>=0 && y<m && graph[x][y]=='W' && !status[x][y]){
                    status[x][y]=true;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

1.2 BFS习题

离开中山路

https://www.luogu.com.cn/problem/P1746

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int a,b,c,d;
int graph[N][N];
int dist[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n;
void bfs(){
  queue<PII> q;
  q.push({a,b});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<4;i++){
      int x=t.first+dx[i];
      int y=t.second+dy[i];
      if(x>=1 && x<=n && y>=1 && y<=n
      && dist[x][y]==-1 && graph[x][y]==0){
        dist[x][y]=dist[t.first][t.second]+1;
        q.push({x,y});
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n;
  for(int i=1;i<=n;i++){
    string s;
    cin>>s;
    for(int j=1;j<=n;j++){
      graph[i][j]=s[j-1]-'0';
    }
  }
  
  cin>>a>>b>>c>>d;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      dist[i][j]=-1;
    }
  }
  
  dist[a][b]=0;
  bfs(); 
  cout<<dist[c][d]<<endl;
    
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=1010;
    public static int n;
    public static int [][]graph=new int[N][N];
    public static int [][]dist=new int[N][N];
    public static int []dx={1,-1,0,0};
    public static int []dy={0,0,1,-1};
    public static int a,b,c,d;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            String s=sc.next();
            for(int j=1;j<=n;j++){
                graph[i][j]=s.charAt(j-1)-'0';
            }
        }
        a=sc.nextInt();
        b=sc.nextInt();
        c=sc.nextInt();
        d=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j]=-1;
            }
        }
        dist[a][b]=0;
        bfs();
        System.out.println(dist[c][d]);
    }
    public static void bfs(){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(a,b));
        while (!q.isEmpty()){
            Node node=q.poll();
            for(int i=0;i<4;i++){
                int x=node.x+dx[i];
                int y=node.y+dy[i];
                if(x>=1 && x<=n && y>=1 && y<=n
                && dist[x][y]==-1 && graph[x][y]==0){
                    dist[x][y]=dist[node.x][node.y]+1;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

马的遍历

https://www.luogu.com.cn/problem/P1443

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=420;
int n,m,x,y;
int dist[N][N];
int dx[8]={1,2,1,2,-1,-1,-2,-2};
int dy[8]={2,1,-2,-1,2,-2,1,-1};
void bfs(){
  queue<PII> q;
  q.push({x,y});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<8;i++){
      x=t.first+dx[i];
      y=t.second+dy[i];
      if(x>=1 && x<=n && y>=1 && y<=m
      && dist[x][y]==-1){
        dist[x][y]=dist[t.first][t.second]+1;
        q.push({x,y});
      } 
    }
  }
  
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m>>x>>y;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      dist[i][j]=-1;
    }
  } 
  dist[x][y]=0;
  bfs();
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cout<<dist[i][j]<<" "; 
    }
    cout<<endl;
  }
  
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=410;
    public static int n,m,x,y;
    public static int[][]dist=new int[N][N];
    public static int []dx={1,2,1,2,-1,-1,-2,-2};
    public static int []dy={2,1,-2,-1,2,-2,1,-1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        x=sc.nextInt();
        y=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dist[i][j]=-1;
            }
        }
        dist[x][y]=0;
        bfs();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(dist[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void bfs(){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        while (!q.isEmpty()){
            Node t=q.poll();
            for(int i=0;i<8;i++){
                x=t.x+dx[i];
                y=t.y+dy[i];
                if(x>=1 && x<=n && y>=1 && y<=m
                && dist[x][y]==-1){
                    dist[x][y]=dist[t.x][t.y]+1;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
    
}

image.gif

血色先锋队

https://www.luogu.com.cn/problem/P1332

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=520;
int n,m,a,b;
int dist[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<PII> q;
void bfs(){
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<4;i++){
      int x=t.first+dx[i];
      int y=t.second+dy[i];
      if(x>=1 && x<=n && y>=1 && y<=m
      && dist[x][y]==-1){
        dist[x][y]=dist[t.first][t.second]+1;
        q.push({x,y});
      }
    }
  } 
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m>>a>>b;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      dist[i][j]=-1;
    }
  } 
  
  for(int i=1;i<=a;i++){
    int x,y;
    cin>>x>>y;
    q.push({x,y});
    dist[x][y]=0;
  }
  bfs();
  for(int i=1;i<=b;i++){
    int x,y;
    cin>>x>>y;
    cout<<dist[x][y]<<endl;
  }
  
  
  
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=520;
    public static int n,m,a,b;
    public static int[][]dist=new int[N][N];
    public static int []dx={0,0,1,-1};
    public static int []dy={1,-1,0,0};
    public static Queue<Node> q=new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        a=sc.nextInt();
        b=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dist[i][j]=-1;
            }
        }
        for(int i=1;i<=a;i++){
            int x,y;
            x=sc.nextInt();
            y=sc.nextInt();
            q.offer(new Node(x,y));
            dist[x][y]=0;
        }
        bfs();
        for(int i=1;i<=b;i++){
            int x,y;
            x=sc.nextInt();
            y=sc.nextInt();
            System.out.println(dist[x][y]);
        }
    }
    public static void bfs(){
        while(!q.isEmpty()){
            Node t=q.poll();
            for(int i=0;i<4;i++){
                int x=t.x+dx[i];
                int y=t.y+dy[i];
                if(x>=1 && x<=n && y>=1 && y<=m && dist[x][y]==-1){
                    dist[x][y]=dist[t.x][t.y]+1;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

填涂颜色

https://www.luogu.com.cn/problem/P1162

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=40;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n;
int graph[N][N];
bool status[N][N];
void bfs(int x,int y){
  queue<PII> q;
  q.push({x,y});
  while(q.size()){
    auto t=q.front();
    q.pop();
    for(int i=0;i<4;i++){
      x=t.first+dx[i];
      y=t.second+dy[i];
      if(x>=0 && x<=n+1 && y>=0 && y<=n+1
      && !status[x][y] && graph[x][y]==0){
        status[x][y]=true;
        q.push({x,y});
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>graph[i][j];
    }
  }
  bfs(0,0);
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(graph[i][j]==0 && !status[i][j]){
        graph[i][j]=2;
      }
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cout<<graph[i][j]<<" ";
    }
    cout<<endl;
  }
  
  return 0;
}

image.gif

import java.util.*;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int N=35;
    public static int n;
    public static int [][]graph=new int[N][N];
    public static boolean[][] status=new boolean[N][N];
    public static int dx[]={0,0,1,-1};
    public static int dy[]={1,-1,0,0};
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                graph[i][j]=sc.nextInt();
            }
        }
        bfs(0,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(graph[i][j]==0 && !status[i][j]){
                    graph[i][j]=2;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                System.out.print(graph[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void bfs(int x,int y){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        while (!q.isEmpty()){
            Node t=q.poll();
            for(int i=0;i<4;i++){
                x=t.x+dx[i];
                y=t.y+dy[i];
                if(x>=0 && x<=n+1 && y>=0 && y<=n+1
                        && !status[x][y] &&graph[x][y]==0){
                    status[x][y]=true;
                    q.offer(new Node(x,y));
                }
            }
        }
    }
}

image.gif

Meteor Shower S

https://www.luogu.com.cn/problem/P2895

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f3f;
typedef pair<int,int> PII;
const int N=320;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dist[N][N];
int fire[N][N];
int m;
int bfs(){
  queue<PII> q;
  q.push({0,0});
  while(q.size()){
    auto t=q.front();
    q.pop();
    if(fire[t.first][t.second]==MAX){
      return dist[t.first][t.second];
    }
    for(int i=0;i<4;i++){
      int a=t.first+dx[i];
      int b=t.second+dy[i];
      if(a>=0 && b>=0 && fire[a][b]==MAX){
        return dist[t.first][t.second]+1;
      }
      if(a>=0 && b>=0 && dist[a][b]==MAX
      && dist[t.first][t.second]+1<fire[a][b]){
        dist[a][b]=dist[t.first][t.second]+1;
        q.push({a,b});
      }
    }
  }
  return -1;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>m;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dist[i][j]=MAX;
      fire[i][j]=MAX;
    }
  }
  dist[0][0]=0;
  
  for(int i=1;i<=m;i++){
    int x,y,t;
    cin>>x>>y>>t;
    fire[x][y]=min(fire[x][y],t);
    for(int i=0;i<4;i++){
      int a=x+dx[i];
      int b=y+dy[i];
      if(a>=0 && b>=0) fire[a][b]=min(fire[a][b],t);
    }
  }
  int res=bfs();
  cout<<res<<endl;
    
  
  return 0;
}

image.gif

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node{
    int x,y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main {
    public static final int MAX=0x3f3f3f3f;
    public static final int N=320;
    public static int m;
    public static int[] dx={0,0,1,-1};
    public static int[] dy={1,-1,0,0};
    public static int[][] fire=new int[N][N];
    public static int[][] dist=new int[N][N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        m=sc.nextInt();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                fire[i][j]=MAX;
                dist[i][j]=MAX;
            }
        }
        dist[0][0]=0;
        for(int i=1;i<=m;i++){
            int x,y,t;
            x=sc.nextInt();
            y=sc.nextInt();
            t=sc.nextInt();
            fire[x][y]=Math.min(fire[x][y],t);
            for(int j=0;j<4;j++){
                int a=x+dx[j];
                int b=y+dy[j];
                if(a>=0 && b>=0){
                    fire[a][b]=Math.min(fire[a][b],t);
                }
            }
        }
        int res=bfs();
        System.out.println(res);
    }
    public static int bfs() {
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(0,0));
        while(!q.isEmpty()){
            Node t=q.poll();
            if(fire[t.x][t.y]==MAX){
                return dist[t.x][t.y];
            }
            for(int i=0;i<4;i++){
                int a=t.x+dx[i];
                int b=t.y+dy[i];
                if(a>=0 && b>=0 && fire[a][b]==MAX){
                    return dist[t.x][t.y]+1;
                }
                if(a>=0 && b>=0 && dist[a][b]==MAX && dist[t.x][t.y]+1<fire[a][b]){
                    dist[a][b]=dist[t.x][t.y]+1;
                    q.offer(new Node(a,b));
                }
            }
        }
        return -1;
    }
}

image.gif

八数码

https://www.acwing.com/problem/content/847/

代码模板(C++/Java):

#include<bits/stdc++.h>
using namespace std;
const int N=10;
typedef pair<int,int> PII;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
int bfs(string s){
  queue<string> q;
  unordered_map<string,int> d;
  q.push(s);
  d[s]=0;
  string end="12345678x";
  while(q.size()){
    auto t=q.front();
    q.pop();
    if(t==end) return d[t];
    int distance=d[t];
    int k=t.find('x');
    int x=k/3,y=k%3;
    for(int i=0;i<4;i++){
      int a=x+dx[i],b=y+dy[i];
      if(a>=0 && a<3 && b>=0 && b<3){
        swap(t[a*3+b],t[k]);
        if(!d.count(t)){
          d[t]=distance+1;
          q.push(t);
        }
        swap(t[a*3+b],t[k]);
      }
    }
  }
  return -1;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  char c[2];
  string s;
  for(int i=0;i<9;i++){
    cin>>c;
    s+=c;
  }
  cout<<bfs(s)<<endl;
  return 0;
}

image.gif

import java.util.*;
public class Main {
    public static Queue<String> q=new LinkedList<>();
    public static Map<String,Integer> map=new HashMap<>();
    public static int[]dx={0,0,1,-1};
    public static int[]dy={1,-1,0,0};
    public static String target="12345678x";
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < 9; i++) {
            String s=sc.next();
            sb.append(s);
        }
        int res=bfs(sb.toString());
        System.out.println(res);
    }
    public static int bfs(String s){
        q.add(s);
        map.put(s,0);
        while (!q.isEmpty()){
            String cur=q.poll();
            int d=map.get(cur);
            if(cur.equals(target)){
                return map.get(cur);
            }
            int k=cur.indexOf("x");
            int x=k/3;
            int y=k%3;
            for (int i = 0; i < 4; i++) {
                int a=x+dx[i];
                int b=y+dy[i];
                if(a>=0 && a<3 && b>=0 && b<3){
                    char[]arr=cur.toCharArray();
                    char t=arr[k];
                    arr[k]=arr[a*3+b];
                    arr[a*3+b]=t;
                    String str=new String(arr);
                    if(!map.containsKey(str)){
                        q.add(str);
                        map.put(str,d+1);
                    }
                }
            }
        }
        return -1;
    }
}

image.gif

相关文章
|
8月前
|
消息中间件 Dubbo Java
深入剖析RocketMQ2-实战案例
本文介绍了一个基于电商场景的订单和支付系统实现方案。系统采用SpringBoot+Dubbo+Zookeeper+RocketMQ技术栈,重点解决分布式系统中的数据一致性问题。在订单模块,通过预订单生成、库存扣减、优惠券使用、余额扣减等步骤完成下单流程,并利用RocketMQ实现失败补偿机制。支付模块处理第三方支付回调,通过消息队列异步更新订单状态。系统通过分布式事务保证数据一致性,采用线程池优化消息发送性能,并提供完整的测试方案验证系统功能。本文详细阐述了技术架构、数据库设计、核心业务流程以及异常处理机制
|
8月前
|
机器学习/深度学习 存储 人工智能
大模型应用开发1-认识大模型
摘要: 本文系统介绍了大模型的基础概念、本地部署及API调用方法。首先阐述了AI及神经网络的基本原理,重点解析了Transformer架构及其在大语言模型(LLM)中的应用。其次详细对比了三种模型使用方案(开放API/云部署/本地部署)的优缺点,并以Ollama为例演示了本地部署流程,包括模型管理、交互指令和GPU加速配置。最后说明了大模型API调用规范,列举了主流大模型产品及其应用场景,强调大模型在自然语言处理、内容生成等领域的优势,以及与传统编程结合开发智能应用的可能性。全文涵盖技术原理到实践操作,为大
|
8月前
|
消息中间件 SQL 存储
深入剖析RocketMQ1-基础使用
本文介绍了RocketMQ消息队列的核心概念、集群部署及消息发送示例。首先阐述了消息队列的作用包括应用解耦、流量削峰和数据分发,并对比了不同MQ产品的优缺点。重点讲解了RocketMQ的集群架构模式,详细演示了双主双从集群(2m-2s同步双写)的搭建过程,包括环境配置、Broker参数设置和集群启动。最后通过代码示例展示了基本消息发送接收、顺序消息、延迟消息、批量消息、消息过滤和事务消息的实现方式,为开发者提供了RocketMQ的实用指南。
|
8月前
|
存储 Prometheus 监控
Prometheus+Grafana构建企业级监控方案
Prometheus是一种开源的监控系统,通过时间序列数据库存储指标数据,支持多维数据模型和PromQL查询语言。其工作原理是通过HTTP拉取应用暴露的指标(如SpringBoot的Actuator端点),并持久化存储。示例展示了SpringBoot整合Prometheus的过程,包括依赖引入、配置暴露指标端点,以及通过Docker部署应用。最后介绍了Prometheus与Grafana的集成,通过配置数据源和仪表板实现可视化监控。整个方案适用于内网部署,支持服务发现和多种中间件监控。
|
8月前
|
存储 监控 NoSQL
手撕Redis底层3-持久化机制与集群化方案
Redis持久化与集群架构详解 摘要:本文系统介绍了Redis的高可用架构方案。首先讲解了RDB和AOF两种持久化机制的特点及实现原理,RDB通过快照实现数据备份,AOF记录操作日志保证数据安全。其次详细阐述了主从集群的搭建过程、全量同步与增量同步机制,以及哨兵监控系统的故障转移流程。最后分析了分片集群架构,包括散列插槽的数据分布策略、集群扩容方法和故障处理机制。通过三种集群方案的对比,展示了Redis如何实现高并发、高可用及海量数据存储。文章还提供了Spring Boot集成Redis集群的实践指导,包括
|
8月前
|
前端开发 Java Nacos
微服务基础2-网关路由
本文介绍了微服务架构中网关技术与配置管理的解决方案。主要内容包括:1)网关路由功能,通过统一入口解决前端联调问题,实现请求转发;2)网关鉴权机制,利用JWT统一处理登录校验,避免各服务重复开发;3)Nacos配置管理,实现共享配置、热更新和动态路由功能。通过网关路由和过滤器链实现请求路由与鉴权,利用Nacos集中管理配置并支持动态更新,解决了微服务架构下的入口统一、身份认证和配置维护难题。最终实现无需重启即可更新配置和路由的能力,提升了系统的灵活性和可维护性。
|
8月前
|
安全 NoSQL Java
基于JWT+SpringSecurity整合一个单点认证授权机制
本文介绍了基于JWT和SpringSecurity的授权认证机制架构设计。系统采用RBAC权限模型,通过5张表描述用户-角色-权限关系。认证流程包含登录验证、IP检查、密码匹配等环节,使用JWT生成token并保存用户信息到Redis。授权部分利用@PreAuthorize注解和PermissionService实现权限校验,支持单权限、多权限及角色验证。整体架构通过过滤器链实现无状态认证,兼顾安全性和灵活性,为开发者提供了完整的认证授权解决方案。
|
8月前
|
消息中间件 存储 监控
详解Kafka2-进阶机制
本文摘要: 文章详细介绍了Kafka的分区与副本机制,包括生产者分区写入策略(轮询、随机、按key分配、自定义)、消费者组Rebalance机制及其影响,以及消费者分区分配策略(Range、RoundRobin、Sticky)。同时,阐述了Kafka的副本机制、数据存储形式(Segment结构)、消息不丢失机制(生产者ACK、消费者Offset管理)和数据积压问题。此外,还介绍了Kafka的数据清理策略(日志删除与压缩)、配额限速机制(Quotas)及监控工具Kafka-Eagle的使用方法。通过原理分析与
|
8月前
|
SQL 中间件 API
PythonWeb基础-FastAPI使用
FastAPI是一个基于Python的高性能Web框架,专为构建API接口服务设计。摘要涵盖以下核心内容:1)基础使用包括项目创建、路由定义和参数处理(路径/查询/请求体参数);2)请求响应机制支持JSON、HTML等多种格式;3)中间件和依赖注入实现通用逻辑复用;4)ORM数据库操作完整流程,包含模型定义、CRUD操作和复杂查询(条件/聚合/分页)。框架特性包括异步支持、自动数据验证、类型提示和交互式文档,显著提升开发效率和API性能。
|
8月前
|
人工智能 JavaScript 数据挖掘
大模型应用开发4-MCP实战
MCP(模型上下文协议)是由Anthropic推出的开放标准,旨在解决AI互联领域中智能体与工具间的交互问题。该协议提供统一的数据访问方式,克服传统AI集成碎片化的局限性。MCP支持两种通信机制:stdio(本地进程通信)和SSE(远程服务调用)。其架构包含MCP Host(主应用)、MCP Client(请求转发)和MCP Server(工具执行)三部分。文章详细介绍了MCP的安装配置、工作原理,并通过一个本地舆情分析系统的开发案例,展示了如何实现客户端与服务端的交互。此外还介绍了CherryStudio