华师一附中OI组
标题:
螺旋方阵问题
[打印本页]
作者:
diggersun
时间:
2014-11-18 18:47
标题:
螺旋方阵问题
打印出n*n的螺旋方阵，比如n=5 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
n=6
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
这个题有很多的做法，每种做法都有一定的技巧，大家都可以认真做做，第一种做法，用udlr表示四个方向，四个方向按个数填充。
#include <iostream>
#include <iomanip>
using namespace std;
int a[100][100],n;
int u,d,l,r; //u,d,l,r分别表示上下左右边界
int i,j,k;
void pp()
{
int r,c;///平面图形输出千万不要用x和y
for (r=1; r<=n; r++)
{
for (c=1; c<=n; c++) cout<<setw(4)<<a[r][c];
cout<<endl;
}
}
int main()
{
cin>>n;
u=l=1;d=r=n;
k=1;
while (k<=n*n)
{
for (i=l; i<=r; i++) a[u][i]=k++; //沿着最上面从左到右；
u++; //上界变化
for (i=u; i<=d; i++) a[i][r]=k++; //沿着最右边从上到下；
r--; //右界变化
for (i=r; i>=l; i--) a[d][i]=k++; //沿着最下边从右到左；
d--; //上界变化
for (i=d; i>=u; i--) a[i][l]=k++; //沿着最上面从左到右；
l++; //上界变化
}
pp();
return 0;
}
复制代码
更精妙的做法，用drdc方向数组，设置标志终止位。这段带确实值得研究。
#include <iostream>
#include <iomanip>
using namespace std;
int a[100][100],n;
int dr[]= {0,1,0,-1};
int dc[]= {1,0,-1,0}; ///四个方向
int i,j,r,c,k,d,tr,tc;
void pp()
{
int r,c;///平面图形输出千万不要用x和y
for (r=1; r<=n; r++)
{
for (c=1; c<=n; c++) cout<<setw(4)<<a[r][c];
cout<<endl;
}
}
int main()
{
cin>>n;
a[1][n+1]=a[n+1][n]=a[n][0]=a[0][1]=1;///四个角标标记 第四个没意义
r=1;c=0;
k=1;d=0;
while (k<=n*n)
{
tr=r+dr[d],tc=c+dc[d];///计算下一个位置
if (a[tr][tc]==0) ///能填的话
a[r=tr][c=tc]=k++;
else d=(d+1)%4; ///否则转向
}
pp();
return 0;
}
复制代码
24楼张天旭同学的做法也值得研究一下。
作者:
zhwang
时间:
2018-7-30 23:16
#include<cstdio>
int n;
int a[1001][1001];
int x;
void find(int minn,int maxn)
{
if(minn>=maxn)
{
a[minn][maxn]=n*n;
return;
}
for(int i=minn;i<=maxn;i++)
{
x++;
a[minn][i]=x;
//printf("%d %d:%d\n",minn,i,a[minn][i]);
}
for(int i=minn+1;i<=maxn;i++)
{
x++;
a[i][maxn]=x;
//printf("%d %d:%d\n",i,maxn,a[i][maxn]);
}
for(int i=maxn-1;i>=minn;i--)
{
x++;
a[maxn][i]=x;
//printf("%d ",x);
}
for(int i=maxn-1;i>=minn+1;i--)
{
x++;
a[i][minn]=x;
}
find(minn+1,maxn-1);
}
int main()
{
scanf("%d",&n);
//scanf("%d%d",&x,&y);
int minn=1;
int maxn=n;
a[1][1]=1;
find(minn,maxn);
//printf("%d",a[1][2]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%4d ",a[i][j]);
}
printf("\n");
}
return 0;
}
复制代码
我是按洛谷上的要求写的，用的是递归大法，比较好写一些，目测数学也可以做
作者:
zhwang
时间:
2018-7-30 23:17
刚刚搞那道变形的最小生成树RE一个点差点没把我杀了，拖久了。
作者:
张笑宇
时间:
2018-7-31 09:33
#include<iostream>
using namespace std;
int n,ax,ay;
const int mx=5010;
int a[mx][mx],i,k;
int left_,right_,on_,under_;
int main()
{
cin>>n>>ax>>ay;
left_=1,right_=n,on_=1,under_=n,k=0;
while (k<=n*n-1)
{
for (i=left_; i<=right_; i++)
{
k++;
a[on_][i]=k;
}
on_++;///向下挪一格
for (i=on_;i<=under_;i++)
{
k++;
a[i][right_]=k;
}
right_--;///向左挪一格
for (i=right_;i>=left_;i--)
{
k++;
a[under_][i]=k;
}
under_--;///向上挪一格
for (i=under_;i>=on_;i--)
{
k++;
a[i][left_]=k;
}
left_++;
}
/*
for (i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
*/
cout<<a[ax][ay];
return 0;
}
复制代码
作者:
张笑宇
时间:
2018-7-31 09:33
尴尬
为什么RE了5个点？？？
作者:
zhwang
时间:
2018-7-31 10:33
张笑宇 发表于 2018-7-31 09:33
尴尬为什么RE了5个点？？？
洛谷上是30000*30000，是要分层处理的，模拟不够
作者:
张笑宇
时间:
2018-7-31 10:34
zhwang 发表于 2018-7-31 10:33
洛谷上是30000*30000，是要分层处理的，模拟不够
谢谢大佬
知道了
作者:
吴语林
时间:
2018-7-31 10:35
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,x,y,all=0;
int main()
{
scanf("%d%d%d",&n,&x,&y);
int cen=min(min(x,n-x+1),min(y,n-y+1));
for(int i=1;i<=cen-1;i++)
all+=(n-i*2+1)*4;
if(cen==x)
printf("%d ",all+y-cen+1);
else if(cen==(n-y+1))
printf("%d ",all+n-(cen-1)*2+x-cen);
else if(cen==y)
printf("%d ",all+(n-(cen-1)*2)*3+n-cen-x-1);
else
printf("%d ",all+(n-(cen-1)*2)*2+n-cen-y);
return 0;
}
复制代码
作者:
admin
时间:
2018-7-31 10:52
上完整的程序，使用代码模式
作者:
admin
时间:
2018-7-31 15:51
你们做的都是在什么题呀？
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2
为什么RE了5个点？？？
知道了