?? 1006_wa.cpp
字號:
//找到一個框框之后,把它拿掉,被它覆蓋的地方標上?。?可以代表任何東西。當我們只剩下?和.的時候,工作完成!// hint : all frame are square x == y;#include <iostream>using namespace std;const int maxX = 50;const int maxY = 20;const char c1 = 218 , c2 = 191, c3 = 192, c4 = 217, cv = 179, ch = 196, any = '?'; //提交的時候注意要改char map[maxY + 1][maxX + 1];int l[maxY + 1][maxX + 1], u[maxY + 1][maxX + 1], r[maxY + 1][maxX + 1], d[maxY + 1][maxX + 1], hc[maxY + 1][maxX + 1], vc[maxY + 1][maxX + 1]; // hc vc 用來確保得到的frame中不全是問號 // 如果成功,必須實驗-1的情形int ans[2000][3];int cnt;int totS; // total sybolint min(int a, int b){ return a<b?a:b; }void readIn(){ int i, j;// char c; totS = 0; for( j = 1; j <= maxY; j++ ) { for( i = 1; i <= maxX; i++ ) { cin >> map[j][i]; if( map[j][i] != '.' ) totS++; }// cin >> c; }}void preCalc(){ int i, j;// memset( l,0,sizeof(l) );// memset( u,0,sizeof(u) );// memset( r,0,sizeof(r) );// memset( d,0,sizeof(d) );// memset( hc,0,sizeof(hc) );// memset( vc,0,sizeof(vc) ); for( j = 1; j <= maxY; j++ ) for(i = 1; i <= maxX; i++) { if( map[j][i] != '.' && map[j][i] != any ) hc[j][i] = hc[j][i - 1] + 1, vc[j][i] = vc[j - 1][i] + 1; else hc[j][i] = hc[j][i - 1], vc[j][i] = vc[j - 1][i]; if( map[j][i] == c1 || map[j][i] == c3 ) l[j][i] = i; if( map[j][i] == c2 || map[j][i] == c4 || map[j][i] == ch || map[j][i] == any ) if( map[j][i - 1] == c1 || map[j][i - 1] == c3 || map[j][i - 1] == ch || map[j][i - 1] == any ) l[j][i] = l[j][i-1]; else l[j][i] = i; if( map[j][i] == c1 || map[j][i] == c2 ) u[j][i] = j; if( map[j][i] == c3 || map[j][i] == c4 || map[j][i] == cv || map[j][i] == any ) if( map[j - 1][i] == c1 || map[j - 1][i] == c2 || map[j - 1][i] == cv || map[j - 1][i] == any ) u[j][i] = u[j - 1][i]; else u[j][i] = j; } for( j = maxY; j >= 1; j-- ) for( i = maxX; i >=1; i-- ) { if( map[j][i] == c2 || map[j][i] == c4 ) r[j][i] = i; if( map[j][i] == c1 || map[j][i] == c3 || map[j][i] == ch || map[j][i] == any ) if( map[j][i + 1] == c2 || map[j][i + 1] == c4 || map[j][i + 1] == ch || map[j][i + 1] == any ) r[j][i] = r[j][i+1]; else r[j][i] = i; if( map[j][i] == c3 || map[j][i] == c4 ) d[j][i] = j; if( map[j][i] == c1 || map[j][i] == c2 || map[j][i] == cv || map[j][i] == any ) if( map[j + 1][i] == c3 || map[j + 1][i] == c4 || map[j + 1][i] == cv || map[j + 1][i] == any ) d[j][i] = d[j + 1][i]; else d[j][i] = j; } }void clear( int x, int y ){ if( map[y][x] != '.' && map[y][x] != any ) {totS--; map[y][x] = any;}}bool setans( int a, int b, int c ){ int i; int t = totS; for( i = a; i <= a+c; i++ ) {clear(i, b); clear(i, b+c);} for( i = b+1; i<= b+c-1; i++ ) {clear(a, i); clear(a+c, i);} if(totS == t) return false; else { cnt++; ans[cnt][0] = b-1, ans[cnt][1] = a-1, ans[cnt][2]= c+1; return true; }}void search(){ int i, j, k; for( i = 1; i <= maxX-1; i++ ) for( j = 1; j <= maxY-1; j++) { if( map[j][i] == c1 || map[j][i] == any ) { int range = min( r[j][i] - i, d[j][i] - j ); for( k = range; k >= 1; k-- ) if((map[j][i + k] == c2 || map[j][i + k] == any) && (map[j + k][i] == c3 || map[j + k][i] == any) && (map[j+k][i+k] == c4 || map[j+k][i+k] == any) && u[j+k][i+k] <= j && l[j+k][i+k] <= i && (( vc[j+k][i] > vc[j-1][i] ) || ( hc[j][i+k] > hc[j][i-1] )) )if( setans( i, j, k ) )return; } }} void output(){ int i; cout << cnt << endl; for( i = cnt; i >= 1; i-- ) cout << ans[i][1] << " " << ans[i][0] << " " << ans[i][2] <<endl;}int main(){// freopen("1006.in","r",stdin); readIn(); while( totS > 0 ) { preCalc(); search(); } output(); return 0;}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -