【题解】洛谷P1283 平板涂色（搜索+暴力）

思路

看到n<16 整个坐标<100 肯定想到暴力啊

蒟蒻来一发最简单易懂的题解（因为不会DP哈

首先我们用map数组来存坐标图 **注意前面的坐标需要加1 **

因为输入的是坐标而我们需要的是格子（后面同理)

随后一个结构体存下坐标和颜色还有判断是否涂过

开始搜索时只要从最顶上的几个开始搜索

搜索时有两种情况

当颜色一样时就不用多算拿笔数
当颜色不一样时就要算拿笔数

加上个最优性剪枝可以跑得飞快 33ms

吐槽：这数据也太水了本蒟蒻一开始判断写反了还有75分的说

代码

#include<iostream>

using namespace std;

#define maxn 110

int n,num,ans=1e9+7;

int map[maxn][maxn];//存图

struct sq

{

	int x1;

	int x2;

	int y1;

	int y2;

	int col;

	bool vis;//判断是否涂色

}a[21];

void cinn()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2>>a[i].col;

		a[i].vis=0;

		for(int j=a[i].x1+1;j<=a[i].x2;j++)

		    for(int k=a[i].y1+1;k<=a[i].y2;k++)

		    map[j][k]=a[i].col;//保存颜色

	}

}

void add(int x)//涂色后为0

{

	for(int j=a[x].x1+1;j<=a[x].x2;j++)

		    for(int k=a[x].y1+1;k<=a[x].y2;k++)

		    map[j][k]=0;

}

void del(int x)//清除涂色

{

	for(int j=a[x].x1+1;j<=a[x].x2;j++)

		    for(int k=a[x].y1+1;k<=a[x].y2;k++)

		    map[j][k]=a[x].col;

}

int pd(int x)//判断上面是否涂色

{

	for(int i=a[x].y1+1;i<=a[x].y2;i++)

	if(map[a[x].x1][i]!=0) return 0;//如果上面有一格没涂就不能涂这格

	return 1;

}

void dfs(int now,int sum,int cnt)

{

	if(sum>ans) return;//最优性剪枝

	if(cnt==n)//当所有矩形都涂色完成

	{

		ans=sum; //不用取最小值 因为前面的剪枝已经把大于最优解剪掉了

		return;

    }

    for(int i=1;i<=n;i++)//枚举矩形

    {

		if(!a[i].vis&&pd(i))//如果这个矩形没有被涂色 且可以涂

		{

			if(a[i].col==a[now].col&&pd(i))//当颜色一样时

			{

				a[i].vis=1;

				add(i);

				dfs(i,sum,cnt+1);//拿笔数不用加1 而已涂矩形要加1

				a[i].vis=0;

				del(i);

			}

			if(a[i].col!=a[now].col&&pd(i))//当颜色不一样时

			{

				a[i].vis=1;

				add(i);

				dfs(i,sum+1,cnt+1);//都要加1

				a[i].vis=0;

				del(i);

			}

		}

    }

}

int main()

{

	cinn();

	for(int i=1;i<=n;i++)

	{

		if(!a[i].x1&&!a[i].vis)//只要从最上面开始搜索

		{

			a[i].vis=1;

			add(i);

			dfs(i,1,1);//先取第一个

			a[i].vis=0;

			del(i);

		}

	}

	cout<<ans;

}

巴特西

【题解】洛谷P1283 平板涂色（搜索+暴力）

思路

代码

最新文章

热门文章