這個題目就是一個模擬的過程
每次找到一個完整的矩形然后把這個矩形拿出。拿走的地方全部變成*
*號是可以表示為任何字母
然后哦一次下去就可以了。
優(yōu)于把題目讀錯了結(jié)果一直就在wa
先開始把題目讀成了每個矩形左上角的點和右下角的點必定會出現(xiàn)
結(jié)果題目的意思是出現(xiàn)的所有點中最靠左的x和最靠上的y組成的就是左上角
同樣最靠右的最靠下的組成的就是又下角的坐標。
1
#include<stdio.h>
2#include<iostream>
3#include<string.h>
4#include<string>
5using namespace std;
6
struct C
{int x,y,a,b;};
7char data[50][50],use[30],p[30];
8C a[30];
9string q[100],temp;
10int l,ans,n,m;
11void di(int k)
12{
13
//printf("%d\n",k);
14 int i,f,j;
15 int map[50][50];
16 if(k==l)
17
{
18 q[ans++]=p;
19 return;
20
}
21 for(j=25;j>=0;j--)
22 {
23 if(use[j]||a[j].a==-1)continue;
24 f=1;
25 for(i=a[j].x;i<=a[j].a;i++)if((data[i][a[j].y]!=j+'A') && data[i][a[j].y]!='*'){f=0;break;}
26 if(f==0)continue;
27 for(i=a[j].x;i<=a[j].a;i++)if((data[i][a[j].b]!=j+'A') && data[i][a[j].b]!='*'){f=0;break;}
28 if(f==0)continue;
29 for(i=a[j].y;i<=a[j].b;i++)if((data[a[j].x][i]!=j+'A') && data[a[j].x][i]!='*'){f=0;break;}
30 if(f==0)continue;
31 for(i=a[j].y;i<=a[j].b;i++)if((data[a[j].a][i]!=j+'A') && data[a[j].a][i]!='*'){f=0;break;}
32 //printf("");for(i=a[j].y;i<=a[j].b;i++)printf("%c",data[a[j].a][i]);printf("\n");
33 if(f==0)continue;
34 //printf("%d\n",j);
35 for(i=a[j].x;i<=a[j].a;i++)
36 {
37 map[i][a[j].y]=data[i][a[j].y];
38 map[i][a[j].b]=data[i][a[j].b];
39 }
40 for(i=a[j].y;i<=a[j].b;i++)
41 {
42 map[a[j].x][i]=data[a[j].x][i];
43 map[a[j].a][i]=data[a[j].a][i];
44 }
45
46 for(i=a[j].x;i<=a[j].a;i++)
47 {
48 data[i][a[j].y]='*';
49 data[i][a[j].b]='*';
50 }
51 for(i=a[j].y;i<=a[j].b;i++)
52 {
53 data[a[j].x][i]='*';
54 data[a[j].a][i]='*';
55 }
56
57 use[j]=1;
58 p[l-k-1]=j+'A';
59 di(k+1);
60 //printf("%d\n",j);
61 use[j]=0;
62 for(i=a[j].x;i<=a[j].a;i++)
63 {
64 data[i][a[j].y]=map[i][a[j].y];
65 data[i][a[j].b]=map[i][a[j].b];
66 }
67 for(i=a[j].y;i<=a[j].b;i++)
68 {
69 data[a[j].x][i]=map[a[j].x][i];
70 data[a[j].a][i]=map[a[j].a][i];
71 }
72 }
73
74
}
75int main()
76{
77 //freopen("input.txt","r",stdin);
78 int i,j;
79 char ch;
80 while(scanf("%d%d",&n,&m)!=EOF)
81 {
82 scanf("%c",&ch);
83 memset(data,0,sizeof(data));
84 memset(use,0,sizeof(use));
85 memset(a,-1,sizeof(a));
86 l=0;ans=0;
87 for(i=0;i<n;i++)
88 {
89 for(j=0;j<m;j++)
90 {
91 scanf("%c",&data[i][j]);
92 if(data[i][j]!='.')
93 {
94
95 if(a[data[i][j]-'A'].x==-1)l++;
96 if(a[data[i][j]-'A'].x==-1||a[data[i][j]-'A'].x>i)a[data[i][j]-'A'].x=i;
97 if(a[data[i][j]-'A'].y==-1||a[data[i][j]-'A'].y>j)a[data[i][j]-'A'].y=j;
98 if(a[data[i][j]-'A'].a==-1||a[data[i][j]-'A'].a<i)a[data[i][j]-'A'].a=i;
99 if(a[data[i][j]-'A'].b==-1||a[data[i][j]-'A'].b<j)a[data[i][j]-'A'].b=j;
100 }
101 }
102 scanf("%c",&ch);
103 }
104 //for(i=0;i<l;i++)printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].a,a[i].b);
105 /**//*
106 for(i=0;i<n;i++)
107 {
108 for(j=0;j<n;j++)printf("%c",data[i][j]);
109 printf("\n");
110 }
111 */
112 p[l]=0;ans=0;
113 di(0);
114 for(i=0;i<ans;i++)
115 for(j=0;j<ans-1;j++)
116 if(q[j]>q[j+1])
117 {
118 temp=q[j];
119 q[j]=q[j+1];
120 q[j+1]=temp;
121 }
122 for(i=0;i<ans;i++)cout<<q[i]<<endl;
123
124
125 // printf("%d\n",ans);
126 }
127 return 0;
128}
129