搜索

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。
搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。

第一题： 排列数字

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n;
vector<int> q;
bool st[10];
void dfs(int t)
{
    if(t==n)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(i);
            dfs(t+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    dfs(0);
    return 0;
}

第二题： n-皇后问题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n;
bool col[20];
bool st1[20];
bool st2[20];
char s[20][20];
void dfs(int t)
{
    if(t==n)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<s[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!col[i]&&!st1[t+i]&&!st2[n-t+i])
        {
            col[i]=true;
            st1[t+i]=true;
            st2[n-t+i]=true;
            s[t][i]='Q';
            dfs(t+1);
            s[t][i]='.';
            col[i]=false;
            st1[t+i]=false;
            st2[n-t+i]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            s[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

第三题： 走迷宫

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

第四题 八数码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
string s;
string aim="12345678x";
int bfs()
{
    queue<string> q;
    unordered_map<string,int> d;
    q.push(s);
    d[s]=0;
    while(q.size())
    {
        string t=q.front();
        q.pop();
        int dis=d[t];
        if(t==aim) return dis;
        int k=t.find('x');
        int x=k/3,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)
            {
                swap(t[k],t[a*3+b]);
                if(!d.count(t))
                {
                    d[t]=dis+1;
                    q.push(t);
                }
                swap(t[k],t[a*3+b]);
            }
        }
    }
    return -1;
}
int main()
{
    cin>>s;
    for(int i=1;i<9;i++)
    {
        string c;
        cin>>c;
        s+=c;
    }
    cout<<bfs()<<endl;
    return 0;
}

第五题： 骑士搜索2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[8]={ 0, 1, 0,-1,-1, 1, 1,-1}; 
int dy[8]={-1, 0, 1, 0,-1,-1, 1, 1};
int n,m;
int a[110][110];
bool st[110][110];
void caozuo(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a1=x+dx[i];
        int b1=y+dy[i];
        if(a1<=n&&a1>=1&&b1<=m&&b1>=1&&a[a1][b1]!=2) a[a1][b1]=4;
    }
}

int ans=0;
int bfs()
{
    queue<PII> q;
    q.push({1,1});
    if(a[1][1]==3) ans++;
    st[1][1]=true;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int aa=dx[i]+t.first;
            int bb=dy[i]+t.second;
            if(aa>=1&&aa<=n&&bb>=1&&bb<=m&&a[aa][bb]!=4&&a[aa][bb]!=2)
            {
                if(!st[aa][bb])
                {
                    if(a[aa][bb]==3) ans++;
                    st[aa][bb]=true;
                    q.push({aa,bb});
                }
            }
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==2) caozuo(i,j);
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==4) cout<<"*"<<" ";
            else if(a[i][j]==1) cout<<" "<<" ";
            else cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<bfs()<<endl;
    return 0;
}

第六题： 中国象棋之马

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[8]={-2,-1,1,2,-2,-1,1,2};
int dy[8]={-1,-2,-2,-1,1,2,2,1};
int n,m;
int d[110][110];
int dfs(int x,int y)
{
    memset(d,-1,sizeof(d));
    queue<PII> q;
    q.push({1,1});
    d[1][1]=0;
    while(q.size())
    {
        auto t=q.front();
        int dis=d[t.first][t.second];
        q.pop();
        for(int i=0;i<8;i++)
        {
            int a=dx[i]+t.first;
            int b=dy[i]+t.second;
            if(a>=1&&a<=n&&b>=1&&b<=m)
            {
                if(a==n&&b==m) return dis+1;
                if(d[a][b]==-1)
                {
                    q.push({a,b});
                    d[a][b]=dis+1;
                }
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cout<<dfs(1,1)<<endl;
    return 0;
}

第七题： 矩阵中的距离

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PIII pair<pair<int,int>,int>
const int N=1e6+5;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m;
int a[1010][1010];
bool st[1010][1010];
int d[1010][1010];
void dfs()
{

    queue<PIII> q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                d[i][j]=0;
                q.push({{i,j},0});
                st[i][j]=true;
            }
        }
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int dis=t.second;
        for(int i=0;i<4;i++)
        {
            int a1=dx[i]+t.first.first;
            int b1=dy[i]+t.first.second;
            if(a1>=1&&a1<=n&&b1>=1&&b1<=m)
            {
                if(!st[a1][b1])
                {
                    d[a1][b1]=dis+1;
                    q.push({{a1,b1},dis+1});
                    st[a1][b1]=true;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<d[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    dfs();

    return 0;
}

第八题： 岛屿的最大面积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m;
int a[1010][1010];
bool st[1010][1010];
int ans;
void dfs()
{
    queue<PII> q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1)
            {
                int cnt=1;
                q.push({i,j});
                st[i][j]=true;
                while(q.size())
                {
                    auto t=q.front();
                    q.pop();
                    int dis=t.second;
                    for(int i=0;i<4;i++)
                    {
                        int a1=dx[i]+t.first;
                        int b1=dy[i]+t.second;
                        if(a1>=1&&a1<=n&&b1>=1&&b1<=m&&a[a1][b1]==1)
                        {
                            if(!st[a1][b1])
                            {
                                q.push({a1,b1});
                                cnt++;
                                st[a1][b1]=true;
                            }
                        }
                    }
                }
                ans=max(ans,cnt);
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    dfs();
    return 0;
}

第九题： 跳棋

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[4]={-1,1,-2,2};
int n;
string s="";
string aim="";
int a=0,b=0,c=0;
void dfs()
{
    queue<string> q;
    unordered_map<string,int> ma;
    q.push(s);
    ma[s]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int cnt=ma[t];
        int k=t.find('0');
        for(int i=0;i<4;i++)
        {
            int x=k+dx[i];
            if(x<n&&x>=0)
            {
                swap(t[k],t[x]);
                if(t==aim)
                {
                    cout<<cnt+1<<endl;
                    return;
                }
                if(!ma[t])
                {
                    ma[t]=cnt+1;
                    q.push(t);
                }
                swap(t[k],t[x]);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string ss;
        cin>>ss;
        if(ss=="1") a++;
        else if(ss=="2") b++;
        else c++;
        s+=ss;
    }
    for(int i=1;i<=b;i++) aim=aim+"2";
    for(int i=1;i<=c;i++) aim=aim+"0";
    for(int i=1;i<=a;i++) aim=aim+"1";
    //cout<<s<<endl;
    //cout<<aim<<endl;
    dfs();
    return 0;
}

第十题： 中国象棋之马踏全盘

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[] = {-2,-2,-1,-1, 1, 1, 2, 2}; 
int dy[] = {-1, 1, 2,-2, 2,-2, 1,-1};
int n,m;
int a,b;
int k;
bool st[10][10];
bool dfs(int x,int y,int t)
{
    if(t==k) return 1;
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(!st[a][b]&&a<=n&&a>=1&&b<=m&&b>=1)
        {
            st[a][b]=true;
            if(dfs(a,b,t+1)) return 1;
            st[a][b]=false;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>a>>b;
    k=n*m-1;
    st[a][b]=true;
    cout<<dfs(a,b,0)<<endl;
    return 0;
}

第十一题： Ｂlocks

方法思路:
核心思想：动态维护连通块数量
每次放置一个新格子时：

    检查它的四个邻居：

    如果某个邻居的颜色和当前放置的颜色相同，并且属于未被当前操作访问过的连通块，则：

    该邻居所在的连通块会与当前格子合并，导致总连通块数减少 1。

更新当前格子的颜色和访问标记：

    设置 s[x][y] = color。

    标记 st[x][y] 为当前操作编号（避免重复计算）。

更新连通块数：

    初始假设当前格子是一个新块，ans++。

    每发现一个可以合并的邻居块，ans--（因为合并会减少总块数）。

bfs方法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int n,m;
int ans;
char s[510][510];
int st[510][510];
bool bfs(int x,int y,int color,int step)
{
    if (x<1||x>n||y<1||y>n) return false;
    if (st[x][y]==step||s[x][y]!=color) return false;
    queue<PII> q;
    q.push({x,y});
    st[x][y]=step;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i];
            int b=t.second+dy[i];
            if(a<0||a>n||b<0||b>n) continue;
            if(st[a][b]!=step&&s[a][b]==color)
            {
                st[a][b]=step;
                q.push({a,b});
            }
        }
    }
    return true;
}
int main()
{
    cin>>n>>m;
    for(int t=1;t<=m;t++)
    {
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        c++;
        if (bfs(x+1,y,c,t)) ans--;
        if (bfs(x-1,y,c,t)) ans--;
        if (bfs(x,y+1,c,t)) ans--;
        if (bfs(x,y-1,c,t)) ans--;
        ans++;
        s[x][y]=c;
        st[x][y]=t;
        printf("%d\n",ans);
    }
    return 0;
}

dfs方法：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 555;
int grid[MAXN][MAXN];  
int visited[MAXN][MAXN];  
int n, m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool dfs(int x, int y, int color, int step) 
{
    if (x < 1 || x > n || y < 1 || y > n) return false;
    if (visited[x][y] == step) return false;
    if (grid[x][y] != color) return false;

    visited[x][y] = step;
    for (int i = 0; i < 4; i++) 
    {
        dfs(x + dx[i], y + dy[i], color, step);
    }
    return true;
}

int main() {
    cin >> n >> m;
    int ans = 0;

    for (int step = 1; step <= m; step++) 
    {
        int color, x, y;
        scanf("%d%d%d",&color,&x,&y);
        color++; 

        if (dfs(x + 1, y, color, step)) ans--;
        if (dfs(x - 1, y, color, step)) ans--;
        if (dfs(x, y + 1, color, step)) ans--;
        if (dfs(x, y - 1, color, step)) ans--;

        ans++; 
        visited[x][y] = step;  
        grid[x][y] = color;    

        printf("%d\n",ans);
    }
    return 0;
}