题目链接:
https://vjudge.net/problem/UVA-12113
题意:
能不能用不超过6张2x2的方纸在4x4的方格中摆出给定的图形?
题解:
最多放9个正方形,暴力枚举每个正方形放这9个中的哪个位置 坐标要想一想, 因为是覆盖,所以空格也要赋值
代码:
#include <bits/stdc++.h>
using namespace std;
typedef
long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF =
0x3f3f3f3f;
const ll INFLL =
0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
ll x=
0,f=
1;
char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=getchar();}
return x*f;
}
const int maxn =
1e5+
10;
char mp[
5][
9],p1[
5][
9];
int vis[
9];
bool ok(){
for(
int i=
0; i<
5; i++)
for(
int j=
0; j<
9; j++)
if(mp[i][j] != p1[i][j])
return false;
return true;
}
bool dfs(
int step){
if(ok())
return true;
char p2[
5][
9];
for(
int i=
0; i<
5; i++)
for(
int j=
0; j<
9; j++)
p2[i][j] = p1[i][j];
if(step >=
6)
return false;
int i;
for(i=
0; i<
9; i++){
if(vis[i])
continue;
vis[i] =
1;
int r=i/
3, c=
2*(i%
3)+
1;
p1[r][c] = p1[r][c+
2] = p1[r+
2][c] = p1[r+
2][c+
2] =
'_';
p1[r+
1][c-
1] = p1[r+
2][c-
1] = p1[r+
1][c+
3] = p1[r+
2][c+
3] =
'|';
p1[r+
1][c] = p1[r+
1][c+
1] = p1[r+
1][c+
2] = p1[r+
2][c+
1] =
' ';
if(dfs(step+
1))
return true;
vis[i] =
0;
for(
int i=
0; i<
5; i++)
for(
int j=
0; j<
9; j++)
p1[i][j] = p2[i][j];
}
return false;
}
int main(){
int cas=
0;
while(
1){
for(
int i=
0; i<
5; i++){
gets(mp[i]);
if(mp[i][
0] ==
'0')
return 0;
}
for(
int i=
0; i<
5; i++)
for(
int j=
0; j<
9; j++)
p1[i][j] =
' ';
MS(vis);
if(dfs(
0)) printf(
"Case %d: Yes\n",++cas);
else printf(
"Case %d: No\n",++cas);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-50360.html