卫星地图

题目描述

一张矩形的卫星地图，有M行N列。行列中的0表示空地，1表示有建筑。有3种类型的建筑:

L型: 仅在一行上占据连续的若干个格子，长度至少为2，至多为N

C型：仅在一列上占据连续的若干个格子，长度至少为2，至多为M

S型：仅占据单个格子。

在同一行上或者同一列上可以出现多个建筑。

不同的建筑不会相邻，相邻是指上，下，左，右，以及左上，左下，右上，右下等八个方向。

求出不同类型的建筑的数量及长度。

输入格式

第1行：2个整数M和N

接下来M行，每行N个0或1，数字之间由空格分开

输出格式

第1行：先输出S，再输出1个整数表示S型建筑的数量，如果没有，则不输出。

接下来若干行，每行依次表示L型建筑的长度以及该长度的建筑数量，按长度递增的顺序输出，中间用一个空格分开，如果没有L型建筑，则不输出。

接下来若干行，每行依次表示C型建筑的长度以及该长度的建筑数量，按长度递增的顺序输出. 中间用一个空格分开，如果没有C型建筑，则不输出。

样例

样例输入

12 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0

样例输出

S 1
L 2 1
L 5 1
L 6 1
C 3 2
C 4 1

数据范围与提示

1≤ M，N ≤ 1000

分析

当我们看到这道题后就会想到用map去解决他，因为在计算L建筑和C建筑的时候需要从小到大输出，这时候，我们把建筑的长度作为“键”，把每种建筑的数量作为“值”。
这个题坑很多，这是我第一遍做的代码

第一遍的代码——20

#include 
using namespace std;
map l, c;
map::iterator it;
int a[1005][1005], cns, cnl, cnc, cnlm, cncm, n, m, i, j;
int main() {cin >> n >> m;for (i = 1; i <= n; i++)for (j = 1; j <= m; j++) cin >> a[i][j];for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (a[i - 1][j] == 0 && a[i + 1][j] == 0 && a[i][j - 1] == 0 && a[i][j + 1] == 0 && a[i][j] == 1)cns++, a[i][j] = 2;cout << 'S' << " " << cns << endl;for (i = 1; i <= n; i++) {for (j = 1; j <= m; j++) {if (a[i][j] == 1)a[i][j] = 2, cnl++;elsecnl = 0;cnlm = max(cnlm, cnl);}l[cnlm]++;cnlm = 0, cnl = 0;}for (it = l.begin(); it != l.end(); it++) {if (it->first >= 2 && it->second != 0)cout << "L"<< " " << it->first << " " << it->second << endl;}for (i = 1; i <= n; i++) {for (j = 1; j <= m; j++) {if (a[j][i] >= 2)cnc++;elsecnc = 0;cncm = max(cncm, cnc);}c[cncm]++;cncm = 0, cnc = 0;}for (it = c.begin(); it != c.end(); it++) {if (it->first >= 2 && it->second != 0)cout << "C"<< " " << it->first << " " << it->second << endl;}
}

这个代码的计算顺序是S—L—C，最初始的思路是将已经计算过的格子标记为2，但是这篇代码漏洞百出
1.在计算C建筑的时候，m和n搞反了。
2.忽略了同一列或行上有两种同样的建筑的情况，本片代码直接取最大值，所以WA了。

第二遍代码——40分

#include 
using namespace std;
map l, c;
map::iterator it;
int a[1005][1005], cns, cnl, cnc, cnlm, cncm, n, m, i, j;
int main() {cin >> n >> m;for (i = 1; i <= n; i++)for (j = 1; j <= m; j++) cin >> a[i][j];for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (a[i - 1][j] != 1 && a[i + 1][j] != 1 && a[i][j - 1] != 1 && a[i][j + 1] != 1 && a[i][j] == 1)cns++, a[i][j] = 2;if (cns != 0)cout << 'S' << " " << cns << endl;for (i = 1; i <= n; i++) {for (j = 1; j <= m; j++) {if (a[i][j] == 1)cnl++;elsecnl = 0;cnlm = max(cnlm, cnl);}if (cnlm != 0)l[cnlm]++;cnlm = 0, cnl = 0;}for (it = l.begin(); it != l.end(); it++) {if (it->first >= 2 && it->second != 0)cout << "L"<< " " << it->first << " " << it->second << endl;}for (i = 1; i <= n; i++) {for (j = 1; j <= m; j++) {if (a[j][i] == 1)cnc++;elsecnc = 0;cncm = max(cncm, cnc);}if (cncm != 0)c[cncm]++;cncm = 0, cnc = 0;}for (it = c.begin(); it != c.end(); it++) {if (it->first >= 2 && it->second != 0)cout << "C"<< " " << it->first << " " << it->second << endl;}
}

改动：
1.在给map赋值时，加了cnt！=0的条件，但本质上一样。
2.在S建筑输出的时候，加了！=0的条件，这样在没有这种建筑的时候不输出。

这时候，整体程序的思路和判断条件都有些复杂
这是50分的代码，改变了顺序为了方便标记，但后来发现可以用更简单的代码

#include
using namespace std;
mapl,c;
map::iterator it;
int a[1005][1005],cns,cnl,cnc,cnlm,cncm,n,m,i,j;
int main(){cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>a[i][j];for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(a[i][j]==1&&(a[i][j+1]!=0||a[i][j-1]!=0))cnl++,a[i][j]=2;else cnl=0;cnlm=max(cnlm,cnl);}if(cnlm!=0)l[cnlm]++;cnlm=0,cnl=0;}for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(a[j][i]==1&&(a[j+1][i]!=0||a[j-1][i]!=0)) a[j][i]=2,cnc++;else cnc=0;cncm=max(cncm,cnc);}if(cncm!=0)c[cncm]++;cncm=0,cnc=0;}for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]==1)cns++;if(cns!=0)  cout<<'S'<<" "<if(it->first>=2&&it->second!=0)cout<<"L"<<" "<first<<" "<second<if(it->first>=2&&it->second!=0)cout<<"C"<<" "<first<<" "<second<

#include 
using namespace std;
map l, c;                                                              //map用来存储l建筑和c建筑的数据
map::iterator it;
int a[1005][1005], cnt, cntm, n, m, i, j;
int main() {cin >> n >> m;for(i = 1; i <= n; i++)                                                      for(j = 1; j <= m; j++)cin >> a[i][j];                                                      //输入用二维数组存放for (i = 1; i <= n; i++) {                                                    //判断lfor (j = 1; j <= m; j++) {if (a[i][j] == 1 && (a[i][j + 1] != 0 || a[i][j - 1] != 0))           //如果为1且前后为1，则满足条件，为了避免是s建筑的情况cnt++, a[i][j] = 2;                                               //如果满足，将当前位置做标记，并且cnt++;else {if (cnt >= 2)                                                     //否则需要把现有值也存储进map中，这是为了避免同一行或同一列出现两个同样建筑的情况l[cnt]++;cnt = 0;                                                          //当前值为0，说明不连续，cnt就可归0}                                            }if (cnt >= 2)                                                             //行末或列末为1情况单独判断l[cnt]++;cnt = 0;}for (i = 1; i <= m; i++) {                                                    //判断cfor (j = 1; j <= n; j++) {if (a[j][i] == 1 && (a[j + 1][i] != 0 || a[j - 1][i] != 0))           //c是列，所以需要把i,j反过来a[j][i] = 2, cnt++;                                         else {if (cnt >= 2)c[cnt]++;cnt = 0;}}if (cnt >= 2)c[cnt]++;cnt = 0;}for (i = 1; i <= n; i++)                                                       //判断sfor (j = 1; j <= m; j++)if (a[i][j] == 1)                                                      //因为前两种都标记了，所以不需要附加条件cnt++;if (cnt != 0)                                                                  //题目要求为0不输出cout << 'S' << " " << cnt << endl;                                  for (it = l.begin(); it != l.end(); it++) {          if (it->second != 0)                                                       //用map迭代器输出,长度不为0cout << "L" << " " << it->first << " " << it->second << endl;}for (it = c.begin(); it != c.end(); it++) {if (it->second != 0)cout << "C" << " " << it->first << " " << it->second << endl;}
}