T11 图像旋转
描述
输入一个n行m列的黑白图像，将它顺时针旋转90度后输出。
输入
第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。
接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。
输出
m行，每行n个整数，为顺时针旋转90度后的图像。相邻两个整数之间用单个空格隔开。
样例输入 样例输出
样例
以矩阵元素坐标为例：
1,1 1,2 1,3 顺时针旋转后为 2,1 1,1
2,1 2,2 2,3 2,2 1,2
2,3 1,3
所以输出时第一重循环i正着循环每一列，第二重循环j倒着循环每一行，依次输出（j，i）
#include<iostream>
using namespace std;
int n,m,a[][];
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>a[i][j];
for(int i=;i<=m;i++)
{
for(int j=n;j>=;j--)
cout<<a[j][i]<<' ';
cout<<endl;
}
}
T12 变换的矩阵
描述
有一个N x N（N为奇数，且1 <= N <= 10）的矩阵，矩阵中的元素都是字符。这个矩阵可能会按照如下的几种变幻法则之一进行变幻（只会变幻一次）。
现在给出一个原始的矩阵，和一个变幻后的矩阵，请编写一个程序，来判定原始矩阵是按照哪一种法则变幻为目标矩阵的。
1. 按照顺时针方向旋转90度；
如：
1 2 3 7 4 1
4 5 6 变幻为 8 5 2
7 8 9 9 6 3
2. 按照逆时针方向旋转90度；
如：
1 2 3 3 6 9
4 5 6 变幻为 2 5 8
7 8 9 1 4 7
3. *元素不变（如下例中的 5），其他元素（如下例中的3）与“以*元素为中心的对应元素”（如下例中的7）互换；
如：
1 2 3 9 8 7
4 5 6 变幻为 6 5 4
7 8 9 3 2 1
4. 保持原始矩阵，不变幻；
5. 如果 从原始矩阵 到 目标矩阵 的变幻，不符合任何上述变幻，请输出5
输入
第一行：矩阵每行/列元素的个数 N；
第二行到第N+1行：原始矩阵，共N行，每行N个字符；
第N+2行到第2*N+1行：目标矩阵，共N行，每行N个字符；
输出
只有一行，从原始矩阵 到 目标矩阵 的所采取的 变幻法则的编号。
样例输入 a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
y x w v u
t s r q p
o n m l k
j i h g f
e d c b a
样例输出
样例
方法1（比较麻烦，但是快用时1ms，时间复杂度n²—4n²）：记录下原始矩阵每一种变换情况后的矩阵，然后与目标矩阵对比
1,1 1,2 1,3 顺时针旋转后为 2,1 1,1
2,1 2,2 2,3 2,2 1,2
2,3 1,3
所以记录时第一重循环i正着循环每一列，第二重循环j倒着循环每一行，依次记录a[j][i]
1,1 1,2 1,3 逆时针旋转后为 1,3 2,3
2,1 2,2 2,3 1,2 2,2
1,1 2,1
所以记录时第一重循环i正着循环每一行，第二重循环j倒着循环每一列，依次记录a[i][j]
情况3也就是将整个矩阵旋转180°，所以记录时两重循环都倒着循环
#include<iostream>
#include<cstdlib>
using namespace std;
int n;
char a[][],b[][],c[][];
void case1()
{
int x=,y=;
for(int i=;i<=n;i++)
{
x++;y=;
for(int j=n;j>=;j--)
c[x][++y]=a[j][i];
for(int k=;k<=n;k++)
if(c[x][k]!=b[x][k])
return;
}
cout<<'';
exit();
}
void case2()
{
int x=,y=;
for(int i=n;i>=;i--)
{
x++;y=;
for(int j=;j<=n;j++)
c[x][++y]=a[j][i];
for(int k=;k<=n;k++)
if(c[x][k]!=b[x][k])
return ;
}
cout<<'';
exit();
}
void case3()
{
int x=,y=;
for(int i=n;i>=;i--)
{
x++;y=;
for(int j=n;j>=;j--)
c[x][++y]=a[i][j];
for(int k=;k<=n;k++)
if(c[x][k]!=b[x][k])
return;
}
cout<<'';
exit();
}
void case4()
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(a[i][j]!=b[i][j])
return;
cout<<'';
exit();
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>b[i][j];
case1();
case2();
case3();
case4();
cout<<'';
return ;
}
1
方法2（代码较短，但慢一点，9ms，时间复杂度，固定4n²）：
省去方法1中的记录，直接根据目标矩阵与原矩阵变换后元素的位置关系判断。所以需要判断完所有位置才能出结果
顺时针旋转目标数组b[i][j]对应原数组a[n-j+1][i]
逆时针旋转目标数组b[i][j]对应原数组a[j][n-i+1]
中心对称目标数组b[i][j]对应原数组a[n-i+1][n-j+1]
#include<iostream>
using namespace std;
int n;
char a[][],b[][];
bool p[];
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>b[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(b[i][j]!=a[n-j+][i]) p[]=true;
if(b[i][j]!=a[j][n-i+]) p[]=true;
if(b[i][j]!=a[n-i+][n-j+]) p[]=true;
if(b[i][j]!=a[i][j]) p[]=true;
}
for(int i=;i<=;i++)
if(!p[i])
{
cout<<i;return ;
}
cout<<'';
}
T13 图像模糊处理
描述
给定n行m列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：
1. 四周最外侧的像素点灰度值不变；
2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。
输入
第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。
接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。
输出
n行，每行m个整数，为模糊处理后的图像。相邻两个整数之间用单个空格隔开。
样例输入 样例输出
样例
四舍五入可以用函数round，也可以用printf（”.0lf“，x）；
#include<iostream>
#include<cmath>
using namespace std;
int n,m,a[][],b[][];
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(i==||i==n||j==||j==m)
b[i][j]=a[i][j];
else
{
double r=((double)a[i][j]+a[i-][j]+a[i+][j]+a[i][j-]+a[i][j+])/;
b[i][j]=round(r);
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
cout<<b[i][j]<<' ';
cout<<endl;
}
}
T14 扫雷游戏地雷数计算
描述
扫雷游戏是一款十分经典的单机小游戏。它的精髓在于，通过已翻开格子所提示的周围格地雷数，来判断未翻开格子里是否是地雷。
现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格的周围格地雷数。
注：每个格子周围格有八个：上、下、左、右、左上、右上、左下、右下。
输入
第一行包含两个整数n和m，分别表示雷区的行数和列数。1 <= n <= 100, 1 <= m <= 100。
接下来n行，每行m个字符，‘*’表示相应格子中是地雷，‘？’表示相应格子中无地雷。字符之间无任何分隔符。
输出
n行，每行m个字符，描述整个雷区。若相应格中是地雷，则用‘*’表示，否则用相应的周围格地雷数表示。字符之间无任何分隔符。
样例输入 *??
???
?*?
样例输出
* *
样例
两种思路：1、统计出每个地雷的位置，以地雷为基准，周围8个非地雷的格子+1。预测应该比第二种方法快
2、以每一个格子为基准，枚举周围8个格子。时间复杂度O（8n²）
在此只提供第一种方法的代码
#include<iostream>
using namespace std;
int n,m,b[][],cnt;
int dx[]={-,-,-,,,,,};
int dy[]={-,,,,,,-,-};
int x[],y[];
char a[][];
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='*')
{
x[++cnt]=i;y[cnt]=j;
}
}
for(int i=;i<=cnt;i++)
{
int xx=x[i],yy=y[i];
for(int j=;j<;j++)
{
int nx=xx+dx[j],ny=yy+dy[j];
if(nx>&&nx<=n&&ny>&&ny<=m&&a[nx][ny]!='*')
b[nx][ny]++;
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
if(a[i][j]=='*') cout<<'*';
else cout<<b[i][j];
cout<<endl;
}
}
T15 细菌的繁殖与扩散
描述
在边长为9的正方形培养皿中，正中心位置有m个细菌。假设细菌的寿命仅一天，但每天可繁殖10个后代，而且这10个后代，有两个分布在原来的单元格中，其余的均匀分布在其四周相邻的八个单元格中。求经过n(1≤n≤4)天后，细菌在培养皿中的分布情况。
输入
输入为两个整数，第一个整数m表示中心位置细菌的个数（2 ≤ m ≤ 30），第二个整数n表示经过的天数（1 ≤ n ≤ 4）。
输出
输出九行九列整数矩阵，每行的整数之间用空格分隔。整个矩阵代表n天后细菌在培养皿上的分布情况。
样例输入 样例输出
样例
三维数组a[k][i][j]代表第k天后矩阵[i,j]位置的细菌数，每次更新时，由于细菌寿命只有一天，所以新的a[k][i][j]=a[k-1][i][j]*2+a[k-1][ni][nj],ni,nj为[i,j]周围的八个单元格
#include<iostream>
using namespace std;
int m,n;
int dx[]={-,-,-,,,,,};
int dy[]={-,,,,,,-,-};
int a[][][];
int main()
{
cin>>m>>n;
a[][][]=m;
for(int k=;k<=n;k++)//枚举每一天
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)//枚举每个单元格
{
a[k][i][j]=*a[k-][i][j];//留在原单元格的2个
for(int l=;l<;l++)//周围的8个单元格
{
int nx=i+dx[l],ny=j+dy[l];
if(nx>&&nx<=&&ny>&&ny<=)
a[k][i][j]+=a[k-][nx][ny];
}
}
}
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
cout<<a[n][i][j]<<' ';
cout<<endl;
}
}
上面的代码是9ms，下面这个是0ms，搞不懂哪里拖延了时间，期待各位的指点
#include<bits/stdc++.h>
using namespace std;
int G[][],m,n,a[][],dx[]={,,,-,,-,,-},dy[]={-,,,,,-,-,};
int main()
{
cin>>m>>n;G[][]=m;
while(n--)
{
memset(a,,sizeof(a));
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
a[i][j]+=G[i][j]*;
for(int k=;k<;k++)
a[i+dx[k]][j+dy[k]]+=G[i][j];
}
memcpy(G,a,sizeof(a));
}
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
cout<<G[i][j]<<' ';
cout<<endl;
}
return ;
}
2
T16 矩阵石头剪刀布
描述
Bart的妹妹Lisa在一个二维矩阵上创造了新的文明。矩阵上每个位置被三种生命形式之一占据：石头，剪刀，布。每天，上下左右相邻的不同生命形式将会发生战斗。在战斗中，石头永远胜剪刀，剪刀永远胜布，布永远胜石头。每一天结束之后，败者的领地将被胜者占领。
你的工作是计算出n天之后矩阵的占据情况。
输入
第一行包含三个正整数r，c，n，分别表示矩阵的行数、列数以及天数。每个整数均不超过100。
接下来r行，每行c个字符，描述矩阵初始时被占据的情况。每个位置上的字符只能是R，S，P三者之一，分别代表石头，剪刀，布。相邻字符之间无空格。
输出
输出n天之后的矩阵占据情况。每个位置上的字符只能是R，S，P三者之一，相邻字符之间无空格。
样例输入 RRR
RSR
RRR
样例输出
RRR
RRR
RRR
样例
a[k][i][j]代表第k天，矩阵[i,j]的字符
枚举每一天每一对格子的情况，因为它只会被能够赢它的字符更新，且能更新它的字符只有一个，所以可以每次在四周找能更新它的字符，找到更新，找不到就保持原状
因为R,S,P互相都有胜负关系，所以每一天每个格子只能被更新一次，所以更新了可以立刻停止对这个格子四周的搜索。例：R遇到P，R在今天结束时更新成P，但今天这个格子遇到R，平局，遇到S，胜利，自己不会被更新
所以确定a[k][i][j]时，要由a[k-1][i-1][j],a[k-1][i][j+1],a[k-1][i+1][j],a[k-1][i][j-1]决定，注意是k-1，即上一天的情况。例：PRS，P可以更新R，R可以更新S，由于枚举的顺序，所以先变成PPS，然后枚举到S时，因为这还是同一天，所以要用原来的R来更新S，而不是用S来更新P
由于a[k][i][j]的情况只与a[k-1][][]有关，所以可以用滚动数组优化空间
#include<iostream>
#include<cstring>
using namespace std;
int r,c,n;
int dx[]={-,,,};
int dy[]={,,,-};
char a[][][];
void work(int last/*滚动数组*/,int h/*行*/,int l/*列*/,char win/*目标字符，即可以更新它的字符*/)
{
int now=(last+)%;
int ok=;
for(int i=;i<;i++)
{
if(a[last][h+dx[i]][l+dy[i]]==win) ok=,a[now][h][l]=win;
if(ok) break;//更新了便可退出
}
if(!ok) a[now][h][l]=a[last][h][l];
}
int main()
{
cin>>r>>c>>n;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
cin>>a[][i][j];
for(int k=;k<=n;k++)
{
memset(a[k%],'\0',sizeof(a[k%]));//滚动数组要初始化
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
switch(a[(k-)%][i][j])
{
case 'R':work((k-)%,i,j,'P');break;//解释：若这个格子为R，那要以这个格子的坐标为基准，在四周找能更新它的P
case 'S':work((k-)%,i,j,'R');break;
case 'P':work((k-)%,i,j,'S');break;
}
}
for(int i=;i<=r;i++)
{
for(int j=;j<=c;j++)
cout<<a[n&][i][j];
cout<<endl;
}
}
起初滚动数组的更新误放到了work函数里，应该在这一天还未开始时清空掉上两天的数据，即每天更新一次，放在work函数里成了每枚举一个格子更新一次
T17 最好的草
描述
奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。
在牧场地图中，每个草丛要么是单个“#”，要么是有公共边的相邻两个“#”。给定牧场地图，计算有多少个草丛。
例如，考虑如下5行6列的牧场地图
.#....
..#...
..#..#
...##.
.#....
这个牧场有5个草丛：一个在第一行，一个在第二列横跨了二、三行，一个在第三行，一个在第四行横跨了四、五列，最后一个在第五行。
输入
第一行包含两个整数R和C，中间用单个空格隔开。
接下来R行，每行C个字符，描述牧场地图。字符只有“#”或“.”两种。
输出
输出一个整数，表示草丛数。
样例输入 .#....
..#...
..#..#
...##.
.#....
样例输出
样例
裸的dfs搜索题，注意别忘了判重
#include<iostream>
using namespace std;
int r,c;
int dx[]={-,,,};
int dy[]={,,,-};
char a[][];
bool v[][];
int s;
void dfs(int x,int y)
{
for(int i=;i<;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>&&nx<=r&&ny>&&ny<=c&&a[nx][ny]=='#'&&!v[nx][ny])
{
v[nx][ny]=true;
dfs(nx,ny);
}
}
}
int main()
{
cin>>r>>c;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
cin>>a[i][j];
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
if(a[i][j]=='#'&&!v[i][j])
{
v[i][j]=true;
dfs(i,j);
s++;
}
cout<<s;
}
T18 肿瘤面积
描述
在一个正方形的灰度图片上，肿瘤是一块矩形的区域，肿瘤的边缘所在的像素点在图片中用0表示。其它肿瘤内和肿瘤外的点都用255表示。现在要求你编写一个程序，计算肿瘤内部的像素点的个数（不包括肿瘤边缘上的点）。已知肿瘤的边缘平行于图像的边缘。
输入
只有一个测试样例。第一行有一个整数n，表示正方形图像的边长。其后n行每行有n个整数，取值为0或255。整数之间用一个空格隔开。已知n不大于1000。
输出
输出一行，该行包含一个整数，为要求的肿瘤内的像素点的个数。
样例输入 样例输出
样例
首先搜索确定矩形框架，由题意得只有一个矩阵，所以按顺序搜到的第一个等于0的点一定是矩阵的左上角的顶点，假设为（i，j）。以（i，j）为基础，竖着在第j列搜，搜到一个点不是0或超出边界，即确定了矩阵左下角的顶点（x，j）。横着在第i行搜，搜到一个点不是0或超出边界，即确定了矩阵右上角的顶点（i，y），右下角的顶点为（x，y）。所以这个矩阵一共包含像素点（x-i+1）*（y-j+1）个，边缘有(x-i+y-j)*2个像素点，两个做差就是内部的像素点个数
#include<iostream>
using namespace std;
int n,a[][];
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(!a[i][j])
{
int x=i,y=j;
while(x<=n)
{
x++;
if(a[x][j]) break;
}
x--;//前面x先++，在判断，所以break时x是已经超出边界或不符合条件的，所以要减1
while(y<=n)
{
y++;
if(a[i][y]) break;
}
y--;//减1的原理同上
int tot=(x-i+)*(y-j+);//总共的像素点
int bian=(x-i+y-j)*;//边缘上的像素点
cout<<tot-bian;
return ;
}
}
T19 肿瘤检测
描述
一张CT扫描的灰度图像可以用一个N*N（0 < N <= 100）的矩阵描述，矩阵上的每个点对应一个灰度值（整数），其取值范围是0-255。我们假设给定的图像中有且只有一个肿瘤。在图上监测肿瘤的方法如下：如果某个点对应的灰度值小于等于50，则这个点在肿瘤上，否则不在肿瘤上。我们把在肿瘤上的点的数目加起来，就得到了肿瘤在图上的面积。任何在肿瘤上的点，如果它是图像的边界或者它的上下左右四个相邻点中至少有一个是非肿瘤上的点，则该点称为肿瘤的边界点。肿瘤的边界点的个数称为肿瘤的周长。现在给定一个图像，要求计算其中的肿瘤的面积和周长。
输入
输入第一行包含一个正整数N（0 < N <= 100），表示图像的大小；接下来N行，每行包含图像的一行。图像的一行用N个整数表示（所有整数大于等于0，小于等于255），两个整数之间用一个空格隔开。
输出
输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。
样例输入 样例输出
样例
方法1：BFS，但是这道题题目描述有点问题，实际测试数据中有多个肿瘤，BFS只按一个肿瘤算只能拿4分。
方法2：枚举每一个元素，小于等于50则s+1，枚举完了s即为肿瘤面积，对于每一个小于等于50的元素判断是否是边界，是则c+1，最后c为周长，此种方法可以忽略有几个肿瘤的干扰，比BFS慢了2ms
#include<iostream>
using namespace std;
int n;
int dx[]={-,,,};
int dy[]={,,,-};
int a[][];
bool v[][];
int s,bian;
void dfs(int x,int y)
{
s++;
int ok=;
for(int i=;i<;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>&&nx<=n&&ny>&&ny<=n&&a[nx][ny]<=)
{
if(!v[nx][ny])
{
v[nx][ny]=true;
dfs(nx,ny);
}
}
else ok=;
}
if(ok) bian++;
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(a[i][j]<=&&!v[i][j])
{
v[i][j]=true;
dfs(i,j);
}
cout<<s<<' '<<bian;
return ;
}
1
#include<iostream>
using namespace std;
int main()
{
int n,i,j,k,dx[]={,-,,},dy[]={,,,-},a[][],s=,c=;
cin>>n;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
cin>>a[i][j];
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(a[i][j]<=)
{
s++;
for(k=;k<;k++)
if(a[i+dx[k]][j+dy[k]]>||i==||i==n||j==||j==n)
{
c++;
break;
}
}
cout<<s<<" "<<c;
}
2
T20 反反复复
描述
Mo和Larry发明了一种信息加密方法。他们首先决定好列数，然后将信息（只包含字母）从上往下依次填入各列，并在末尾补充一些随机字母使其成为一个完整的字母矩阵。例如，若信息是“There's no place like home on a snowy night”并且有5列，Mo会写成：
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
注意Mo只会填入字母，且全部是小写形式。在这个例子中，Mo用字母“x”填充了信息使之成为一个完整的矩阵，当然他使用任何字母都是可以的。
Mo根据这个矩阵重写信息：首先从左到右写下第一行，然后从右到左写下第二行，再从左到右写下第三行……以此左右交替地从上到下写下各行字母，形成新的字符串。这样，例子中的信息就被加密为：toioynnkpheleaigshareconhtomesnlewx。
你的工作是帮助Larry从加密后的信息中还原出原始信息（包括填充的字母）。
输入
第一行包含一个整数（范围2到20），表示使用的列数。
第二行是一个长度不超过200的字符串。
输出
一行，即原始信息。
样例输入 toioynnkpheleaigshareconhtomesnlewx
样例输出
theresnoplacelikehomeonasnowynightx
样例
将加密后的字符串横着蛇形存储到数组中，再竖着一列一列的输出来
#include<iostream>
#include<cstring>
using namespace std;
int n;
char a[][],b[];
int main()
{
cin>>n;
cin>>b;
int l=,i=,j=;
int p=;
while(l<strlen(b))//蛇形存储
{
if(p==) j++;
else if(p==) j--;
if(j>n)
{
j=n;p=;i++;
}
if(j<)
{
j=;p=;i++;
}
a[i][j]=b[l];
l++;
}
for(int m=;m<=n;m++)
for(int k=;k<=i;k++)
cout<<a[k][m];
}