T21 二维数组右上左下遍历
描述
给定一个row行col列的整数数组array，要求从array[0][0]元素开始，按从左上到右下的对角线顺序遍历整个数组。
输入
输入的第一行上有两个整数，依次为row和col。
余下有row行，每行包含col个整数，构成一个二维整数数组。
（注：输入的row和col保证0 < row < 100, 0 < col < 100）
输出
按遍历顺序输出每个整数。每个整数占一行。
样例输入 样例输出
样例
先枚举第一行，向左下枚举，再枚举最后一列（除去右上角，因为第一行已经枚举过了）
#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 j=;j<=m;j++)//枚举第一行
{
int i=,k=j;//i：当前行，k：当前列
while(i<=n&&k>)//不超边界
{
cout<<a[i][k]<<endl;
i++;k--;
}
}
for(int i=;i<=n;i++)//最后一列，从第二行开始
{
int j=m,k=i;//j：当前列，k：当前行
while(k<=n&&j>)//不超边界
{
cout<<a[k][j]<<endl;
k++;j--;
}
}
}
第一次枚举最后一列时从第一行开始的，0分。。。。。。
T22 神奇的幻方
描述
幻方是一个很神奇的N*N矩阵，它的每行、每列与对角线，加起来的数字和都是相同的。
我们可以通过以下方法构建一个幻方。（阶数为奇数）
1.第一个数字写在第一行的中间
2.下一个数字，都写在上一个数字的右上方：
a.如果该数字在第一行，则下一个数字写在最后一行，列数为该数字的右一列
b.如果该数字在最后一列，则下一个数字写在第一列，行数为该数字的上一行
c.如果该数字在右上角，或者该数字的右上方已有数字，则下一个数字写在该数字的下方
输入
一个数字N（N<=20）
输出
按上方法构造的2N-1 * 2N-1的幻方
样例输入 样例输出
样例
类似于NOIP2015 Day1 T1，但这道题是2*n-1阶的
#include<iostream>
using namespace std;
int n,a[][];
int main()
{
cin>>n;
a[][n]=;
int i=,x=,y=n;
while(i<=(*n-)*(*n-))
{
if((x==&&y==*n-)||a[x-][y+]) x+=;
else if(x==) x=*n-,y+=;
else if(y==*n-) x-=,y=;
else x-=,y+=;
a[x][y]=i++;
}
for(int k=;k<=*n-;k++)
{
for(int l=;l<=*n-;l++)
cout<<a[k][l]<<' ';
cout<<endl;
}
}
T23 二维数组回形遍历
描述
给定一个row行col列的整数数组array，要求从array[0][0]元素开始，按回形从外向内顺时针顺序遍历整个数组。如图所示：
输入
输入的第一行上有两个整数，依次为row和col。
余下有row行，每行包含col个整数，构成一个二维整数数组。
（注：输入的row和col保证0 < row < 100, 0 < col < 100）
输出
按遍历顺序输出每个整数。每个整数占一行。
样例输入 样例输出
样例
递归遍历即可，一定要注意一个格子只能走一遍以及判断是否输出了所有数，不然会递归死循环
#include<iostream>
using namespace std;
int n,m,a[][];
bool v[][];
bool ok;
bool judge()//判断是否已经输出了所有的数
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(!v[i][j]) return false;
return true;
}
//R向右 ，D向下，L向左，U向上
void dfs(int x,int y,char p)//x：当前行，y：当前列，p判断向哪儿走
{
if(ok) return;//在judge之前先判断是否已经输出了所有点，防止输出完递归回退时多次执行judge函数，浪费时间
ok=judge();
if(p=='R')//可以向右走
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])//不超边界且没有被遍历
{
cout<<a[x][y]<<endl;
v[x][y]=true;
dfs(x,y+,'R');//继续向右走
}
else p='D',dfs(x+,y-,'D');//转为向下走，当执行这个语句时，y已经超出了边界，所以要减1，向下走x+1
}
else if(p=='D')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
cout<<a[x][y]<<endl;
v[x][y]=true;
dfs(x+,y,'D');
}
else p='L',dfs(x-,y-,'L');
}
else if(p=='L')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
cout<<a[x][y]<<endl;
v[x][y]=true;
dfs(x,y-,'L');
}
else p='U',dfs(x-,y+,'U');
}
else if(p=='U')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
cout<<a[x][y]<<endl;
v[x][y]=true;
dfs(x-,y,'U');
}
else p='R',dfs(x+,y+,'R');
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>a[i][j];
dfs(,,'R');
}
T24 蛇形填充数组
描述
用数字1,2,3,4,...,n*n这n2个数蛇形填充规模为n*n的方阵。
蛇形填充方法为：
对于每一条左下-右上的斜线，从左上到右下依次编号1,2,...,2n-1；按编号从小到大的顺序，将数字从小到大填入各条斜线，其中编号为奇数的从左下向右上填写，编号为偶数的从右上到左下填写。
比如n=4时，方阵填充为如下形式：
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
输入
输入一个不大于10的正整数n，表示方阵的行数。
输出
输出该方阵，相邻两个元素之间用单个空格间隔。
注意处理边界情况。
①：超出矩阵上边界，此时位置坐标已经到①出，列与拐弯后的位置的列相等，行少了1，所以行+1，列不变
②：超出矩阵右边界，此时位置坐标已经到②出，行与拐弯后的位置的行少了2行，列多了一列，所以行+2，列-1
③：即超出上边界，又超出右边界，此时位置到③处，我们可以手算一下，若先执行①，再执行②，会到达A处；先执行②，再执行①，会到达B处，而拐弯后的目标位置为B处，所以在程序中，要先判断②的情况，在判断①的情况。
当然为了避免③的情况，也可以另写一个语句直接判断
如果不是边界，直接行减1，列加1
当向左下方填充时，情况类似，就不再写了
#include<iostream>
using namespace std;
int n,a[][];
bool ok;
int main()
{
cin>>n;
int s=,p=;
int x=,y=;
while(s<n*n)//填充，具体解释看上面的题解
{
while(p%==&&s<n*n)
{
ok=false;
s++;
a[x][y]=s;
x++;y--;
if(x>n) x--,y+=,ok=true;
if(y<) y++,ok=true;
if(ok) p++;
}
while(p%==&&s<n*n)
{
ok=false;
s++;
a[x][y]=s;
x--;y++;
if(y>n) x+=,y--,ok=true;
if(x<) x++,ok=true;
if(ok) p++;
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
}
一开始没考虑③的情况，先判断的①，在判断的②，导致对角线拐弯时错行
T25 螺旋加密
描述
Chip和Dale发明了一种文本信息加密技术。他们事先秘密约定好矩阵的行数和列数。接着，将字符按如下方式编码：
1. 所有文本只包含大写字母和空格。
2. 每个字符均赋予一个数值：空格=0，A=1，B=2，……，Y=25，Z=26。
按照下图所示的方式，将每个字符对应数值的5位二进制数依次填入矩阵。最后用0将矩阵补充完整。例如，对于信息“ACM”，行列数均为4时，矩阵将被填充为：
将矩阵中的数字按行连起来形成数字串，完成加密。例子中的信息最终会被加密为：0000110100101100。
输入
一行。首先是两个整数R(1≤R≤20)和C(1≤C≤20)，表示行数和列数。之后是一个只包含大写字母和空格的字符串。字符串的长度≤(R*C)/5。R和C之间以及C和字符串之间均用单个空格隔开。
输出
一行，为加密后的二进制串。注意你可能需要用0将矩阵补充完整。
先将字符串按要求转化为二进制数字，然后再用类似T23二维数组回形遍历的方法把数字存到矩阵里，最后按顺序输出。这种方法虽然麻烦点儿，但比较快，用时0ms
注意数据的读入方式，为了防止读入多余的空格或少读空格，可以将一整行当字符串用gets读进去，再找空格分开。也可以多输入一个getchar（）语句。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,a[][];
char s[];
int ss[];
bool v[][];
int sum;
//R向右 ，D向下，L向左，U向上
void dfs(int x,int y,char p)//x：当前行，y：当前列，p判断向哪儿走
{
if(sum==n*m) return;
if(p=='R')//可以向右走
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])//不超边界且没有被填充
{
a[x][y]=ss[++sum];
v[x][y]=true;
dfs(x,y+,'R');//继续向右走
}
else p='D',dfs(x+,y-,'D');//转为向下走，当执行这个语句时，y已经超出了边界，所以要减1，向下走x+1
}
else if(p=='D')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
a[x][y]=ss[++sum];
v[x][y]=true;
dfs(x+,y,'D');
}
else p='L',dfs(x-,y-,'L');
}
else if(p=='L')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
a[x][y]=ss[++sum];
v[x][y]=true;
dfs(x,y-,'L');
}
else p='U',dfs(x-,y+,'U');
}
else if(p=='U')
{
if(x>&&x<=n&&y>&&y<=m&&!v[x][y])
{
a[x][y]=ss[++sum];
v[x][y]=true;
dfs(x-,y,'U');
}
else p='R',dfs(x+,y+,'R');
}
}
int main()
{
gets(s);
int i;
for(i=;i<strlen(s);i++)//取出行 n
{
if(s[i]!=' ') n=n*+s[i]-'';
else break;
}
int j;
for(j=i+;j<strlen(s);j++)//取出列 m
{
if(s[j]!=' ') m=m*+s[j]-'';
else break;
}
int l=;
for(int k=j+;k<strlen(s);k++) //将字符串转化为二进制
{
if(s[k]==' ')//空格的情况时5个0
for(int u=;u<=;u++) ss[++l]=;
else
{
l+=;//倒着填二进制数
int p=s[k]-,w=;
while(p)
{
ss[l]=p%;
p/=;
l--;
}
while(l%) ss[l]=,l--;//二进制位数有可能不足5位
l+=;//前面倒着填的再加回去
}
}
for(int k=l+;k<=n*m;k++)
ss[k]=;//用0将矩阵补充完整
dfs(,,'R');
for(int p=;p<=n;p++)
for(int k=;k<=m;k++)
cout<<a[p][k];
}
下附简短代码，用时1ms
精简之处1：cin、getchar（）与getline（）的使用省去上面用gets读入在分离的过程
精简之处2:打表提前打出26个英文字符的二进制，利用c++自带的substr函数省去循环5次存储五位二进制的过程
精简之处3：将二进制数存到矩阵中时，以矩阵的一圈为单位，依次以（1,1）、（2,2）、（3,3）等为起点，用while一圈一圈的存储，而不是dfs
精简之处4：题目要求，用0将矩阵补充完整，全局变量定义数组初始值即为0，可以不用管
#include<bits/stdc++.h>
using namespace std;
int n,m,l,c,x,y,t,a[][];
string s,ss,q="";
int main()
{
cin>>n>>m;
getchar();
getline(cin,s);
l=s.size();
for(int k=;k<l;k++)
if(s[k]==' ') ss+="";
else ss+=q.substr(*(s[k]-'A'),);
while(t<*l)
{
c++;x=c;y=c;
while(y+c<=m+&&t<*l){a[x][y]=ss[++t-]-'';y++;}y--;x++;
while(x+c<=n+&&t<*l){a[x][y]=ss[++t-]-'';x++;}x--;y--;
while(y>=c&&t<*l){a[x][y]=ss[++t-]-'';y--;}y++;x--;
while(x>c&&t<*l){a[x][y]=ss[++t-]-'';x--;}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cout<<a[i][j];
return ;
}
2