卫星地图——MAP(c++)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
卫星地图
题目描述
一张矩形的卫星地图有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≤ MN ≤ 1000
分析
当我们看到这道题后就会想到用map去解决他因为在计算L建筑和C建筑的时候需要从小到大输出这时候我们把建筑的长度作为“键”把每种建筑的数量作为“值”。
这个题坑很多这是我第一遍做的代码
第一遍的代码——20
#include <bits/stdc++.h>
using namespace std;
map<int, int> l, c;
map<int, int>::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++;
else
cnl = 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++;
else
cnc = 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 <bits/stdc++.h>
using namespace std;
map<int, int> l, c;
map<int, int>::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++;
else
cnl = 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++;
else
cnc = 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<bits/stdc++.h>
using namespace std;
map<int,int>l,c;
map<int,int>::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'<<" "<<cns<<endl;
for(it=l.begin();it!=l.end();it++){
if(it->first>=2&&it->second!=0)
cout<<"L"<<" "<<it->first<<" "<<it->second<<endl;
}
for(it=c.begin();it!=c.end();it++){
if(it->first>=2&&it->second!=0)
cout<<"C"<<" "<<it->first<<" "<<it->second<<endl;
}
}
我的100分代码略有冗长
#include <bits/stdc++.h>
using namespace std;
map<int, int> l, c; //map用来存储l建筑和c建筑的数据
map<int, int>::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++) { //判断l
for (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++) { //判断c
for (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++) //判断s
for (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迭代器输出,长度不为0
cout << "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;
}
}
在判断条件上做了更改这样就避免了20分代码中同一列或行上有两种同样的建筑的情况写上注释是为了找错神奇的是一写注释就过了
大家一起优化的代码
