链接：http://codeforces.com/contest/370/problem/D
题意：给出n*m的区域，当中填满'w'或'.'，在n*m的区域范围内，添加‘+’，使‘w’和‘+’共同组成正方形边框，注意边框宽度为1，除边框外其他位置都只能为'.'，若存在这样的情况，输出令边框最小的一个方案；若不存在，输出'-1'。
思路：找出存在w的top,bottom,left,right值，构成矩形。令temph为矩形的长，tempv为矩形的宽；
（1）若temph == tempv，则判断框以内是否含‘w’，含‘w’的话输出-1，不含的话，补全‘+’，输出。
（2）若temph > tempv，宽度加大到temph，枚举正方形：top从(top-temp)~top，其中temp = temph - tempv；判断每个正方形框内是否存在'w'，不存在的话补全‘+’，输出该方案。当然正方形超出n*m区域的不算，这里需要判断。
（3）若tempv > temph，同理。
（4）（1）~（3）都找不出一种方案的话自然就输出-1。
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #define N 2005
5 char ch[N][N];
6 int judge(int top, int bottom, int left, int right)
7 {
8 int flag = 1;
9 for(int i = top+1; i<=bottom-1; i++)
10 {
11 for(int j=left+1; j<=right-1; j++)
12 {
13 if(ch[i][j]=='w') {flag = 0; break;}
14 }
15 }
16 return flag;//1---true
17 }
18 int main()
19 {
20 //printf("1111 ");
21 int n,m;
22 int top = 2001, bottom = -1, left = 2001, right = -1, tempi = 0, tempj = 0;
23 //printf("1111 ");
24 scanf("%d%d",&n,&m);
25 getchar();
26 for(int i=1; i<=n; i++)
27 {
28 for(int j=1; j<=m; j++)
29 {
30 ch[i][j] = getchar();
31 if(ch[i][j]=='w')
32 {
33 top = top > i ? i : top;
34 bottom = bottom < i ? i : bottom;
35 left = left > j ? j : left;
36 right = right < j ? j : right;
37 }
38 }
39 getchar();
40 }
41 int flag = 0, flag1 = 1;
42 int temph = right - left + 1, tempv = bottom - top + 1;
43 if(temph == tempv)
44 {
45 for(int i=top+1; i<=bottom-1; i++)
46 for(int j=left+1; j<=right-1; j++)
47 {
48 if(ch[i][j]=='w'){flag = 1; break;}
49 }
50 }
51 else
52 {
53 if(temph > tempv)
54 {
55 int temp = temph - tempv;
56 for(int i=top - temp; i<=top; i++)
57 {
58 if(i<1) continue;
59 if(i+temph-1>n) break;
60 if(judge(i,i+temph-1,left,right))
61 {
62 top = i;
63 bottom = i+temph-1;
64 flag1 = 0;
65 break;
66 }
67 }
68 flag = flag1;
69 }
70 else if(temph < tempv)
71 {
72 int temp = tempv - temph;
73 for(int i=left - temp; i<=left; i++)
74 {
75 if(i<1) continue;
76 if(i+tempv-1>m) break;
77 if(judge(top,bottom,i,i+tempv-1))
78 {
79 left = i;
80 right = i + tempv - 1;
81 flag1 = 0;
82 break;
83 }
84 }
85 flag = flag1;
86 }
87 }
88 if(flag==1)
89 printf("-1 ");
90 else
91 {
92 for(int i=top; i<=bottom; i++)
93 {
94 if(ch[i][left]!='w')
95 ch[i][left] = '+';
96 if(ch[i][right]!='w')
97 ch[i][right]='+';
98 }
99 for(int i=left; i<=right; i++)
100 {
101 if(ch[top][i]!='w')
102 ch[top][i]='+';
103 if(ch[bottom][i]!='w')
104 ch[bottom][i]='+';
105 }
106 for(int i=1; i<=n; i++)
107 {
108 for(int j=1; j<=m; j++)
109 printf("%c",ch[i][j]);
110 printf(" ");
111 }
112 }
113
114 return 0;
115 }
2 #include <cstdlib>
3 #include <cstring>
4 #define N 2005
5 char ch[N][N];
6 int judge(int top, int bottom, int left, int right)
7 {
8 int flag = 1;
9 for(int i = top+1; i<=bottom-1; i++)
10 {
11 for(int j=left+1; j<=right-1; j++)
12 {
13 if(ch[i][j]=='w') {flag = 0; break;}
14 }
15 }
16 return flag;//1---true
17 }
18 int main()
19 {
20 //printf("1111 ");
21 int n,m;
22 int top = 2001, bottom = -1, left = 2001, right = -1, tempi = 0, tempj = 0;
23 //printf("1111 ");
24 scanf("%d%d",&n,&m);
25 getchar();
26 for(int i=1; i<=n; i++)
27 {
28 for(int j=1; j<=m; j++)
29 {
30 ch[i][j] = getchar();
31 if(ch[i][j]=='w')
32 {
33 top = top > i ? i : top;
34 bottom = bottom < i ? i : bottom;
35 left = left > j ? j : left;
36 right = right < j ? j : right;
37 }
38 }
39 getchar();
40 }
41 int flag = 0, flag1 = 1;
42 int temph = right - left + 1, tempv = bottom - top + 1;
43 if(temph == tempv)
44 {
45 for(int i=top+1; i<=bottom-1; i++)
46 for(int j=left+1; j<=right-1; j++)
47 {
48 if(ch[i][j]=='w'){flag = 1; break;}
49 }
50 }
51 else
52 {
53 if(temph > tempv)
54 {
55 int temp = temph - tempv;
56 for(int i=top - temp; i<=top; i++)
57 {
58 if(i<1) continue;
59 if(i+temph-1>n) break;
60 if(judge(i,i+temph-1,left,right))
61 {
62 top = i;
63 bottom = i+temph-1;
64 flag1 = 0;
65 break;
66 }
67 }
68 flag = flag1;
69 }
70 else if(temph < tempv)
71 {
72 int temp = tempv - temph;
73 for(int i=left - temp; i<=left; i++)
74 {
75 if(i<1) continue;
76 if(i+tempv-1>m) break;
77 if(judge(top,bottom,i,i+tempv-1))
78 {
79 left = i;
80 right = i + tempv - 1;
81 flag1 = 0;
82 break;
83 }
84 }
85 flag = flag1;
86 }
87 }
88 if(flag==1)
89 printf("-1 ");
90 else
91 {
92 for(int i=top; i<=bottom; i++)
93 {
94 if(ch[i][left]!='w')
95 ch[i][left] = '+';
96 if(ch[i][right]!='w')
97 ch[i][right]='+';
98 }
99 for(int i=left; i<=right; i++)
100 {
101 if(ch[top][i]!='w')
102 ch[top][i]='+';
103 if(ch[bottom][i]!='w')
104 ch[bottom][i]='+';
105 }
106 for(int i=1; i<=n; i++)
107 {
108 for(int j=1; j<=m; j++)
109 printf("%c",ch[i][j]);
110 printf(" ");
111 }
112 }
113
114 return 0;
115 }
------------------------
不算难题，但也要一开始考虑到所有情况也不容易。4WA