搜索与图论

搜索与图论

DFS

深度优先搜索，一种执着的搜索方法，只有将一条路径走完才回去搜索其他路径。
递归或者栈实现

  1. 全排列

原题来源：【AcWing 842】排列数字

解题思路：使用数字去填补空位，直至空位被填完，说明找到一个可行答案

Code

#include<iostream>
using namespace std;

const int N = 7;
int path[N+1];
bool visited[N+1];
int n;

void dfs(int u){
    if(u==n){
        for (int i = 0; i <n; i ++ )printf("%d ",path[i]);
        puts("");
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            visited[i]=true;
            path[u]=i;
            dfs(u+1);
            visited[i]=false;    //还原现场，不影响其他路径
        }
    
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

  1. n-皇后问题

原题来源：【AcWing 843】n-皇后问题

解题思路：已知每行有且仅有一个皇后。因此只需要考虑在当前行的某一列放置皇后可以满足要求。

Code

col[N]数组表示第i列是否存在过皇后，dg[N]表示（r,i）所在的正对角线是否存在皇后,udg[N]表示（r,i）所在的反对角线是否存在皇后。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;
char g[N][N];
bool col[N],dg[N],udg[N];

int n;

void dfs(int r){
    if(r==n){
        for (int i = 0; i < n; i ++ )puts(g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ ){
        if(!col[i]&&!dg[r+i]&&!udg[n-r+i]){
            g[r][i]='Q';
            col[i]=dg[r+i]=udg[n-r+i]=true;
            dfs(r+1);
            g[r][i]='.';
            col[i]=dg[r+i]=udg[n-r+i]=false;
        }
    }
}

int main()
{
    cin>>n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
        g[i][j]='.';
    dfs(0);
    return 0;
}

BFS

bfs是一种层次搜索方法，逐层搜索答案
由队列实现

  1. 走迷宫

原题来源：【AcWing 844】走迷宫

解题思路：从距离起点最近的几个点开始，直至走到终点

Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int g[N][N],d[N][N];

int n,m,hh,tt=-1;

PII q[N*N];//队列的长度为N*M

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

int bfs(){
    q[++tt]={0,0};
    d[0][0]=0;
    while(hh<=tt){
        auto cur=q[hh++];
        for(int i=0;i<4;i++){
            int x=cur.first+dx[i],y=cur.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
                q[++tt]={x,y};
                d[x][y]=d[cur.first][cur.second]+1;
            }
        }
    }
    return d[n-1][m-1];
}

int main()
{
    memset(d,-1,sizeof d);
    cin>>n>>m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &g[i][j]);
    cout<<bfs()<<endl;
  
}

  1. 8数码问题

原题来源：【AcWing 845】8数码问题

解题思路：该问题的难点有两个，一个是状态表示，另一个是状态转换。

状态表示：用字符串来表示每次变化后的状态，同时使用哈希表代替visited数组查看某一状态是否已经遍历过。

状态转换：每次都是‘x’与其他字符交换位置，因此状态的变化就是‘x’交换位置的过程

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <unordered_map>
#include <queue>
using namespace std;

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

unordered_map<string, int>ump;
queue<string>q;

int bfs(string start){
    string end="12345678x";
  
    ump[start]=0;
    q.push(start);
  
    while(!q.empty()){
        auto t=q.front();
        q.pop();
    
        int distance=ump[t];
        if(t==end)return distance;
    
        int loc=t.find('x');
        int x=loc/3,y=loc%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[loc],t[a*3+b]);
                if(!ump.count(t)){
                    ump[t]=distance+1;
                    q.push(t);
                }
                swap(t[loc],t[a*3+b]);
            }
        }
    }
    return -1;
}

int main()
{
    string start;
    char c;
    for (int i = 0; i < 9; i ++ ){
        cin>>c;
        start+=c;
    }
    cout<<bfs(start)<<endl;
  
}