题目:
给定一个4*4的棋盘和棋盘上所呈现出来的纸张边缘,问用不超过6张2*2的纸能否摆出这样的形状。
思路:
dfs纸的张数,每一张中枚举这张纸左上角这个点的位置,暴力解题就可以了。
这个题的覆盖太恶心了,很容易搞混~~~(因为搞混一直TLE+WA…………)
代码:
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define MAX 1000000000 #define mod 1000000007 #define FRE() freopen("in.txt","r",stdin) #define FRO() freopen("out.txt","w",stdout) using namespace std; typedef long long ll; typedef pair<int,int> P;//first-距离 second-编号 const int maxn = 8; int ans[6][10],mp[5][10]; char str[5][10]; bool judge(){ for(int r=0; r<5; r++){ for(int c=0; c<9; c++){ if(ans[r][c]!=mp[r][c]){ return false; } } } return true; } void copyArray(int a[5][10],int b[5][10]){ for(int i=0; i<5; i++){ for(int j=0; j<9; j++){ a[i][j] = b[i][j]; } } } void putPapper(int x,int y){//-95 |124 mp[x][y+1]=mp[x][y+3]=2; mp[x+2][y+1]=mp[x+2][y+3]=2; //mp[x][y]=mp[x][y+2]=mp[x][y+4]=32; mp[x+2][y+2]=0; mp[x+1][y+1]=mp[x+1][y+2]=mp[x+1][y+3]=0; mp[x+1][y]=mp[x+1][y+4]=1; mp[x+2][y]=mp[x+2][y+4]=1; } bool dfs(int deep){ if(deep>6) return false; for(int i=0; i<3; i++){ for(int j=0; j<=4; j+=2){ int temp[5][10]; copyArray(temp,mp); putPapper(i,j); if(judge())return true; if(dfs(deep+1))return true; copyArray(mp,temp); } } return false; } void check(){ for(int i=0; i<5; i++){ for(int j=0; j<9; j++){ printf("%3d",ans[i][j]); } printf("\n"); } printf("\n\n\n\n"); } int main(){ //FRE(); int kase = 0; while(gets(str[0])&&str[0][0]!=‘0‘){ memset(mp,0,sizeof(mp)); memset(ans,0,sizeof(ans)); for(int i=1; i<5; i++){ gets(str[i]); } for(int i=0; i<5; i++){ for(int j=0; j<9; j++){ if(str[i][j]==‘_‘) ans[i][j]=2; else if(str[i][j]==‘|‘) ans[i][j]=1; } } //check(); if(dfs(1)){ printf("Case %d: Yes\n",++kase); }else{ printf("Case %d: No\n",++kase); } } return 0; }