2022AcWing寒假算法每日一题之2060. 奶牛选美(dfs)

2022AcWing寒假算法每日一题之2060. 奶牛选美(dfs)

题目链接：AcWing2060. 奶牛选美

思路：

1.可以利用反证法证明：当涂色区域数量最小时，必定满足ans = abs(a.x-b.x)+abs(a.y-b.y)-1即求曼哈顿距离，细节注意：-1是因为终点已经是斑点了不用涂色

2.定义vectorpoints[2];用来存储两部分点，再用dfs深搜遍历每个‘X’，将‘X’的坐标存入数组

3.分别遍历两部分的点进行比较，找出最小值

具体代码如下

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 55;
int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//定义方向
char g[N][N];//存储图
vectorpoints[2];//存储两部分点
void dfs(int x,int y,vector&ps)//注意传地址
{
    g[x][y]='.';//遍历过的‘X’设置为‘.’
    ps.push_back({x,y});
    for(int i=0;i<4;i++)
    {
        int a = x+dx[i],b = y+dy[i];
        if(g[a][b]=='X'&&a>=1&&a<=n&&b>=1&&b<=m)//利用边界剪枝
            dfs(a, b, ps);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=1,k=0;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='X')
            {
                dfs(i,j,points[k++]);//points[0]存储第一部分的点，points[1]存储第二部分的点
            }
        }
    }
    int ans = 1e9;
    for(auto& a : points[0])//遍历第一部分点
    {
        for(auto &b : points[1])//遍历第二部分点
        {
            ans=min(ans,abs(a.first-b.first)+abs(a.second-b.second)-1);
        }
    }
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710842.html