如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。
URAL/1006
来自"NOCOW"
< URAL
[编辑] C++程序by zhujf553
#include <iostream> #include <string.h> #include <stdlib.h> using namespace std; const char LU = 218, RU = 191, LB = 192, RB = 217, V = 179, H = 196; const int M = 20, N = 50; char smap[M + 1][N + 1]; int sq[15][3]; int ans = -1; void init() { for(int i = 0 ; i < M ; i++) cin >> smap[i]; } bool check(int ii, int jj, int k) { if(smap[ii][jj] != ',' && smap[ii][jj] != LU) return false; if(smap[ii][jj + k - 1] != ',' && smap[ii][jj + k - 1] != RU) return false; if(smap[ii + k - 1][jj] != ',' && smap[ii + k - 1][jj] != LB) return false; if(smap[ii + k - 1][jj + k - 1] != ',' && smap[ii + k - 1][jj + k - 1] != RB) return false; for(int i = ii + 1 ; i < ii + k - 1 ; i++) { if(smap[i][jj] != ',' && smap[i][jj] != V) return false; if(smap[i][jj + k - 1] != ',' && smap[i][jj + k - 1] != V) return false; } for(int j = jj + 1 ; j < jj + k - 1 ; j++) { if(smap[ii][j] != ',' && smap[ii][j] != H) return false; if(smap[ii + k - 1][j] != ',' && smap[ii + k - 1][j] != H) return false; } bool flag = false; for(int i = ii ; i <= ii + k - 1 ; i++) if(smap[i][jj] != ',' || smap[i][jj + k - 1] != ',') flag = true; for(int j = jj ; j <= jj + k - 1 ; j++) if(smap[ii][j] != ',' || smap[ii + k - 1][j] != ',') flag = true; return flag; } void clear(int ii, int jj, int k) { for(int i = ii ; i <= ii + k - 1 ; i++) smap[i][jj] = smap[i][jj + k - 1] = ','; for(int j = jj ; j <= jj + k - 1 ; j++) smap[ii][j] = smap[ii + k - 1][j] = ','; /*for(int i = 0 ; i < M ; i++) cout << smap[i] << endl; cout << endl;*/ } void work() { int i, j, k, i1, j1, k1; bool flag = true; while(flag) { flag = false; for(k = M ; k >= 2 ; k--) for(i = 0 ; i < M - k + 1 ; i++) for(j = 0 ; j < N - k + 1 ; j++) { if(i == 6 && j == 11 && k == 7) k = 7; if(check(i, j, k)) { ans++; flag = true; sq[ans][0] = i, sq[ans][1] = j, sq[ans][2] = k; clear(i, j, k); goto LLL; } } LLL : ; } cout << ans + 1 << endl; for(i = ans ; i >= 0 ; i--) cout << sq[i][1] << ' ' << sq[i][0] << ' ' << sq[i][2] << endl; } int main() { freopen("ural1006.in", "r", stdin); freopen("ural1006.out", "w", stdout); init(); work(); return 0; }
[编辑] CODE
{受某大牛启发} program cao; const maxn=20; maxm=50; var data:array[0..maxn,0..maxm] of longint; ans:array[0..20000,1..3] of longint; ch:char; total,p:longint; procedure init; var i,j:longint; begin total:=1000; for i:=1 to maxn do begin for j:=1 to maxm do begin read(ch); case ch of #218:data[i,j]:=1; #191:data[i,j]:=2; #192:data[i,j]:=3; #217:data[i,j]:=4; #179:data[i,j]:=5; #196:data[i,j]:=6; #46:dec(total); end; end; readln; end; end; function can(x,y,a:longint):boolean; var i:longint; flag:boolean; begin can:=false; flag:=true; if data[x,y]<>-1 then if data[x,y]<>1 then exit(false); if data[x,y]<>-1 then flag:=false; if data[x,y+a-1]<>-1 then if data[x,y+a-1]<>2 then exit(false); if data[x,y+a-1]<>-1 then flag:=false; if data[x+a-1,y]<>-1 then if data[x+a-1,y]<>3 then exit(false); if data[x+a-1,y]<>-1 then flag:=false; if data[x+a-1,y+a-1]<>-1 then if data[x+a-1,y+a-1]<>4 then exit(false); if data[x+a-1,y+a-1]<>-1 then flag:=false; for i:=2 to a-1 do begin if data[x+i-1,y]<>-1 then if data[x+i-1,y]<>5 then exit(false); if data[x+i-1,y]<>-1 then flag:=false; if data[x+i-1,y+a-1]<>-1 then if data[x+i-1,y+a-1]<>5 then exit(false); if data[x+i-1,y+a-1]<>-1 then flag:=false; if data[x,y+i-1]<>-1 then if data[x,y+i-1]<>6 then exit(false); if data[x,y+i-1]<>-1 then flag:=false; if data[x+a-1,y+i-1]<>-1 then if data[x+a-1,y+i-1]<>6 then exit(false); if data[x+a-1,y+i-1]<>-1 then flag:=false; end; if flag=false then can:=true; end; procedure put(x,y,a:longint); var i:longint; begin if data[x,y]<>-1 then dec(total); data[x,y]:=-1; if data[x,y+a-1]<>-1 then dec(total); data[x,y+a-1]:=-1; if data[x+a-1,y]<>-1 then dec(total); data[x+a-1,y]:=-1; if data[x+a-1,y+a-1]<>-1 then dec(total); data[x+a-1,y+a-1]:=-1; for i:=2 to a-1 do begin if data[x+i-1,y]<>-1 then dec(total); data[x+i-1,y]:=-1; if data[x+i-1,y+a-1]<>-1 then dec(total); data[x+i-1,y+a-1]:=-1; if data[x,y+i-1]<>-1 then dec(total); data[x,y+i-1]:=-1; if data[x+a-1,y+i-1]<>-1 then dec(total); data[x+a-1,y+i-1]:=-1; end; end; procedure find; var i,j,k:longint; begin for i:=1 to maxn do for j:=1 to maxm do for k:=1 to maxm do if can(i,j,k) then begin put(i,j,k); inc(p); ans[p,1]:=j-1; ans[p,2]:=i-1; ans[p,3]:=k; end; end; procedure main; begin p:=0; while total>0 do find; end; procedure print; var i:longint; begin writeln(p); for i:=p downto 1 do writeln(ans[i,1],' ',ans[i,2],' ',ans[i,3]); end; begin init; main; print; end.
[编辑] 原始的暴搜程序
program wx; var i,j,k,m,n,h:longint; s:array[1..20,1..50]of char; f:array[1..20,1..50]of boolean; l:array[1..2000,1..3]of longint; function ff(x,y:longint;c:char):boolean; begin if (s[x,y]<>c)and(s[x,y]<>'?') then exit(false); exit(true); end; function check(x,y,z:longint):boolean; var i:longint; begin if not(ff(x,y,#218)and ff(x+z-1,y,#192) and ff(x,y+z-1,#191)and ff(x+z-1,y+z-1,#217)) then exit(false); for i:=y+1 to y+z-2 do if not(ff(x,i,#196)and ff(x+z-1,i,#196)) then exit(false); for i:=x+1 to x+z-2 do if not(ff(i,y,#179)and ff(i,y+z-1,#179)) then exit(false); for i:=x to x+z-1 do if (s[i,y]<>'?')or(s[i,y+z-1]<>'?') then exit(true); for i:=y+1 to y+z-2 do if (s[x,i]<>'?')or(s[x+z-1,i]<>'?') then exit(true); exit(false); end; function min(x,y:longint):longint; begin if x<y then exit(x); exit(y); end; procedure update(x,y,z:longint); var i:longint; begin for i:=x to x+z-1 do begin s[i,y]:='?'; s[i,y+z-1]:='?'; end; for i:=y+1 to y+z-2 do begin s[x,i]:='?'; s[x+z-1,i]:='?'; end; end; procedure find; begin for i:=1 to n-1 do for j:=1 to m-1 do if ff(i,j,#218) then for k:=2 to min(n-i,m-j)+1 do if check(i,j,k) then begin inc(h); l[h,1]:=i; l[h,2]:=j; l[h,3]:=k; update(i,j,k); exit; end; end; function finish:boolean; begin for i:=1 to n do for j:=1 to m do if not ff(i,j,'.') then exit(false); exit(true); end; begin n:=20;m:=50; for i:=1 to n do readln(s[i]); repeat find; until finish; writeln(h); for i:=h downto 1 do writeln(l[i,2]-1,' ',l[i,1]-1,' ',l[i,3]); end.
