锐客网

  1. 首页 > 睿知 > it技术 > >

UVA - 12113 Overlapping Squares（dfs+回溯）

IT知识squareoverlapoverlapping

与天地兮比寿，与日月兮齐光。这篇文章主要讲述UVA - 12113 Overlapping Squares（dfs+回溯）相关的知识，希望能为你提供帮助。
【UVA - 12113 Overlapping Squares（dfs+回溯）】题目：
给定一个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(" "); } printf(""); }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 ",++kase); }else{ printf("Case %d: No ",++kase); } } return 0; }

 

    推荐阅读


    上一篇：android---动画

    下一篇：snappy