给一个网格的宽W和高H(1<=W,H<=10)以及n(1<=n<=7)个矩形的长ai和宽bi(1<=ai,bi<=10),判断是否可以用矩形铺满整个网格,不能越界和重叠。
输入样例:
5 5 5
1 1
3 3
4 4
2 3
2 5
输出样例:
Yes
一行一行对遍历 以格子为单位 去搜
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=20;
int a[N],b[N];
int mp[N][N];
bool st[N];
int n,h,w;
//看是否合法
bool try1(int x,int y,int a,int b)
{
if(x+a-1>h||y+b-1>w) return false;
for(int i=x;i<=x+a-1;i++)
{
for(int j=y;j<=y+b-1;j++)
{
//说明这个格子已经被占有了 故不行
if(mp[i][j]) return false;
}
}
return true;
}
//利用长 宽 将该点的格子占有--表示该砖被用了
void print(int x,int y,int a,int b)
{
for(int i=x;i<=x+a-1;i++)
{
for(int j=y;j<=y+b-1;j++)
{
mp[i][j]=1;
}
}
}
//恢复现场
void erase(int x,int y,int a,int b)
{
for(int i=x;i<=x+a-1;i++)
{
for(int j=y;j<=y+b-1;j++)
{
mp[i][j]=0;
}
}
}
void dfs(int x,int y)
{
if(y==w+1)
{
y=1;
x++;
}
if(x==h+1)
{
printf("Yes");
exit(0);
}
while(mp[x][y])
{
y++;
if(y==w+1)
{
y=1;
x++;
}
if(x==h+1)
{
printf("Yes");
exit(0);
}
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
//是否可行 可行就用
if(try1(x,y,a[i],b[i]))
{
st[i]=1;
print(x,y,a[i],b[i]);
dfs(x,y+b[i]);
//回溯--恢复现场
st[i]=0;
erase(x,y,a[i],b[i]);
}
if(a[i]==b[i]) continue;
//将长宽换一下
swap(a[i],b[i]);
if(try1(x,y,a[i],b[i]))
{
st[i]=1;
print(x,y,a[i],b[i]);
dfs(x,y+b[i]);
st[i]=0;
erase(x,y,a[i],b[i]);
}
//换回来
swap(a[i],b[i]);
}
}
return ;
}
int main()
{
cin>>n>>h>>w;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
dfs(1,1);
printf("No");
return 0;
}