题目链接:
https://vjudge.net/problem/UVA-12113
题意:
能不能用不超过6张2x2的方纸在4x4的方格中摆出给定的图形？
题解:
最多放9个正方形，暴力枚举每个正方形放这9个中的哪个位置
坐标要想一想， 因为是覆盖，所以空格也要赋值
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 char mp[5][9],p1[5][9]; 19 int vis[9]; 20 21 bool ok(){ 22 for(int i=0; i<5; i++) 23 for(int j=0; j<9; j++) 24 if(mp[i][j] != p1[i][j]) return false; 25 return true; 26 } 27 28 bool dfs(int step){ 29 30 if(ok()) return true; 31 32 char p2[5][9]; 33 for(int i=0; i<5; i++) 34 for(int j=0; j<9; j++) 35 p2[i][j] = p1[i][j]; 36 if(step >= 6) return false; 37 int i; 38 for(i=0; i<9; i++){ 39 if(vis[i]) continue; 40 41 vis[i] = 1; 42 int r=i/3, c=2*(i%3)+1; 43 p1[r][c] = p1[r][c+2] = p1[r+2][c] = p1[r+2][c+2] = '_'; 44 p1[r+1][c-1] = p1[r+2][c-1] = p1[r+1][c+3] = p1[r+2][c+3] = '|'; 45 p1[r+1][c] = p1[r+1][c+1] = p1[r+1][c+2] = p1[r+2][c+1] = ' '; 46 if(dfs(step+1)) return true; 47 48 vis[i] = 0; 49 for(int i=0; i<5; i++) 50 for(int j=0; j<9; j++) 51 p1[i][j] = p2[i][j]; 52 } 53 54 return false; 55 } 56 57 58 int main(){ 59 int cas=0; 60 while(1){ 61 for(int i=0; i<5; i++){ 62 gets(mp[i]); 63 if(mp[i][0] == '0') return 0; 64 } 65 for(int i=0; i<5; i++) 66 for(int j=0; j<9; j++) 67 p1[i][j] = ' '; 68 MS(vis); 69 if(dfs(0)) printf("Case %d: Yes ",++cas); 70 else printf("Case %d: No ",++cas); 71 } 72 73 return 0; 74 } 75 76 // _ _ _ _ # 77 // |_|_|_|_|# 78 // |_|_|_|_|# 79 // |_|_|_|_|# 80 // |_|_|_|_|# 81 // _ _ # 82 // _| |_ # 83 // | |_ _| |# 84 // |_| |_|# 85 // |_ _|_|# 86 // # 87 // _ _ _ # 88 // | |_ _| # 89 // |_| | # 90 // |_ _| #