紫书搜索 习题7-6 UVA - 12113 Overlapping Squares暴力

    xiaoxiao2021-03-25  20

    题目链接:

    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

    最新回复(0)