锐客网

  1. 首页 > 生活百科 > it技术 > >

习题 7-6 UVA - 12113Overlapping Squares

IT知识overlapping习题overlap

青春须早为，岂能长少年。这篇文章主要讲述习题 7-6 UVA - 12113Overlapping Squares相关的知识，希望能为你提供帮助。
【习题 7-6 UVA - 12113Overlapping Squares】 【链接】 我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

先预处理出来一个正方形。
然后每次枚举新加的正方形左上角的坐标就可以。
注意覆盖的规则,控制一下就可以。
然后暴力判断是否相同。
暴力回溯即可(只用回溯一个正方形区域)

【代码】

/* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.Can you promise that the solution is right? At least,the main ideal 4.use the puts(" " ) or putchar() or printf and such things? 5.init the used array or any value? 6.use error MAX_VALUE? 7.use scanf instead of cin/cout? 8.whatch out the detail input require */ /* 一定在这里写完思路再敲代码!!! */ #include < bits/stdc++.h> using namespace std; const int N = 10; const int M = 5; char s[N+5][N+5],now[N+5][N+5]; char square[M+5][M+5]; void init(){ for (int i = 0; i < 3; i++) for (int j = 0; j< 5; j++) square[i][j] = ' ' ; for (int i = 0; i < 2; i++) square[i+1][0] = square[i+1][4] = ' |' ; for (int j = 1; j < 5; j+=2) square[0][j]=square[2][j] = ' _' ; }void Set(int x,int y){ for (int i = 0; i < 3; i++) for (int j = 0; j < 5; j++){ if (i< =0 & & now[i+x][j+y]!=' ' & & square[i][j]==' ' ) continue; now[i+x][j+y] = square[i][j]; } for (int i = 1; i < 2; i++) for (int j = 1; j< 4; j++) now[i+x][j+y] = ' ' ; }bool ok(){ for (int i = 0; i < 5; i++) for (int j = 0; j < 9; j++) if (now[i][j]!=s[i][j]) return false; return true; }void out(){ for (int i = 0; i < 5; i++){ for (int j = 0; j < 9; j++) cout < < now[i][j]; cout < < endl; } cout < < endl; }bool dfs(int dep){ if (dep > 1 & & ok()) return true; if (dep > = 7) return false; int temp[M+5][M+5]; for (int i = 0; i < 3; i++){ for (int j = 0; j < 5; j+=2){ for (int k = 0; k < 3; k++) for (int l = 0; l < 5; l++) temp[k][l] = now[k+i][l+j]; Set(i,j); if (dfs(dep+1)) return true; for (int k = 0; k < 3; k++) for (int l = 0; l < 5; l++) now[k+i][l+j] = temp[k][l]; } } return false; }int main(){ #ifdef LOCAL_DEFINE freopen(" rush_in.txt" , " r" , stdin); #endif ios::sync_with_stdio(0),cin.tie(0); init(); int kase = 0; while (1){ for (int i = 0; i < 5; i++){ cin.getline(s[i],15); if (s[i][0]==' 0' ) return 0; } for (int i = 0; i< 5; i++) for (int j = 0; j < 9; j++) now[i][j] = ' ' ; if (dfs(1)){ cout < < " Case " < < ++kase< < " : Yes" < < endl; }else{ cout < < " Case " < < ++kase< < " : No" < < endl; } } return 0; }


    推荐阅读


    上一篇：用Kotlin破解Android版微信小游戏-跳一跳

    下一篇：Redux和React-Redux的实现（中间件的原理和applyMiddlewareThunk的实现）