P7012题解

Marionette_Guillotin · 2024-02-29 20:15:59 · 题解

P7012题解

原题传送门

发现楼上没有一个写 bfs 滴，于是——

又发现 bfs 难写得很，写了三天连样例都没过（真的很疑惑为什么题目标签里边有 bfs 但没有 dfs）

打了三天，总算不再坚持了，老老实实的写 dfs 吧～

话不多说，进入正题——

思路：dfs + 回溯（只是有一点坑）。遇见一枚白棋就开始搜索，标记黑棋有没有被吃。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define I return
#define love 0
#define FIRESTARS ;
int a[1145][1145],vis[1145][1145],n,m,maxn;
int dx[]={1,-1,1,-1},dy[]={1,-1,-1,1},ddx[]={2,-2,2,-2},ddy[]={2,-2,-2,2}; //方向数组，自己理解 
void dfs(int x,int y,int sum) //xy 为起始坐标，返回值为最多能吃多少棋子
{
    maxn=max(sum,maxn);
    for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i],xx=ddx[i]+x,yy=ddy[i]+y;
            if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&!a[xx][yy]&&a[nx][ny]==2&&!vis[nx][ny])
            {
                vis[nx][ny]=1; //这里我们标记黑棋有没有被吃 
                dfs(xx,yy,sum+1);
                vis[nx][ny]=0; //此题要回溯
            }
        }
}
signed main()
{
    int t;cin>>t;
    n=m=10; //行和列，这样子用更习惯 
    while(t--)
    {
        maxn=0; //千万别忘了初始化！
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;cin>>c;
            if(c=='#')a[i][j]=0;
            if(c=='.')a[i][j]=1;
            if(c=='B')a[i][j]=2;
            if(c=='W')a[i][j]=3;
         } //输入完毕，正片开始 
         for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
            if(a[i][j]==3) //找到了一枚白棋
             {
                a[i][j]=0; //先把它赋值为 0
                //memset(vis,0,sizeof(vis)); 这里不要初始化 vis！初始化多了会 TLE
                dfs(i,j,0);//开始搜索
                a[i][j]=3; //再把它赋值回去
            }
        cout<<maxn<<endl; //输出
    }
    I love FIRESTARS //我爱火星！ 
}

火星提醒您：

搜索大法好，深广要慎选

选择不规范，爆零两行泪