螺旋方阵问题

diggersun

打印出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表示四个方向，四个方向按个数填充。

1. #include <iostream>
   
2. #include <iomanip>
   
3. using namespace std;
   
4. int a[100][100],n;
   
5. int u,d,l,r;  //u,d,l,r分别表示上下左右边界
   
6. int i,j,k;
   
7. void pp()
   
8. {
   
9.     int r,c;///平面图形输出千万不要用x和y
   
10.     for (r=1; r<=n; r++)
    
11.     {
    
12.         for (c=1; c<=n; c++)  cout<<setw(4)<<a[r][c];
    
13.         cout<<endl;
    
14.     }
    
15. }
    
16. int main()
    
17. {
    
18.     cin>>n;
    
19.     u=l=1;d=r=n;
    
20.     k=1;
    
21.     while (k<=n*n)
    
22.     {
    
23.         for (i=l; i<=r; i++) a[u][i]=k++; //沿着最上面从左到右；
    
24.         u++; //上界变化
    
25.         for (i=u; i<=d; i++) a[i][r]=k++; //沿着最右边从上到下；
    
26.         r--; //右界变化
    
27.         for (i=r; i>=l; i--) a[d][i]=k++; //沿着最下边从右到左；
    
28.         d--; //上界变化
    
29.         for (i=d; i>=u; i--) a[i][l]=k++; //沿着最上面从左到右；
    
30.         l++; //上界变化
    
31.     }
    
32.     pp();
    
33.     return 0;
    
34. }
    
35. 
    
36. 
    

复制代码

更精妙的做法，用drdc方向数组，设置标志终止位。这段带确实值得研究。

1. #include <iostream>
   
2. #include <iomanip>
   
3. using namespace std;
   
4. int a[100][100],n;
   
5. int dr[]= {0,1,0,-1};
   
6. int dc[]= {1,0,-1,0}; ///四个方向
   
7. int i,j,r,c,k,d,tr,tc;
   
8. void pp()
   
9. {
   
10.     int r,c;///平面图形输出千万不要用x和y
    
11.     for (r=1; r<=n; r++)
    
12.     {
    
13.         for (c=1; c<=n; c++)  cout<<setw(4)<<a[r][c];
    
14.         cout<<endl;
    
15.     }
    
16. }
    
17. int main()
    
18. {
    
19.     cin>>n;
    
20.     a[1][n+1]=a[n+1][n]=a[n][0]=a[0][1]=1;///四个角标标记 第四个没意义
    
21.     r=1;c=0;
    
22.     k=1;d=0;
    
23.     while (k<=n*n)
    
24.     {
    
25.         tr=r+dr[d],tc=c+dc[d];///计算下一个位置
    
26.         if  (a[tr][tc]==0) ///能填的话
    
27.             a[r=tr][c=tc]=k++;
    
28.         else d=(d+1)%4; ///否则转向
    
29.     }
    
30.     pp();
    
31.     return 0;
    
32. }
    
33. 
    

复制代码

24楼张天旭同学的做法也值得研究一下。

zhwang

1. #include<cstdio>
   
2. int n;
   
3. int a[1001][1001];
   
4. int x;
   
5. void find(int minn,int maxn)
   
6. {
   
7.         if(minn>=maxn)
   
8.         {
   
9.                 a[minn][maxn]=n*n;
   
10.                 return;
    
11.         }
    
12.         for(int i=minn;i<=maxn;i++)
    
13.         {
    
14.                 x++;
    
15.                 a[minn][i]=x;
    
16.                 //printf("%d %d:%d\n",minn,i,a[minn][i]);
    
17.         }
    
18.         for(int i=minn+1;i<=maxn;i++)
    
19.         {
    
20.                 x++;
    
21.                 a[i][maxn]=x;
    
22.                 //printf("%d %d:%d\n",i,maxn,a[i][maxn]);
    
23.         }
    
24.         for(int i=maxn-1;i>=minn;i--)
    
25.         {
    
26.                 x++;
    
27.                 a[maxn][i]=x;
    
28.                 //printf("%d  ",x);
    
29.         }
    
30.         for(int i=maxn-1;i>=minn+1;i--)
    
31.         {
    
32.                 x++;
    
33.                 a[i][minn]=x;
    
34.         }
    
35.         find(minn+1,maxn-1);
    
36. }
    
37. int main()
    
38. {
    
39.         scanf("%d",&n);
    
40.         //scanf("%d%d",&x,&y);
    
41.         int minn=1;
    
42.         int maxn=n;
    
43.         a[1][1]=1;
    
44.         find(minn,maxn);
    
45.         //printf("%d",a[1][2]);
    
46.         for(int i=1;i<=n;i++)
    
47.         {
    
48.                 for(int j=1;j<=n;j++)
    
49.                 {
    
50.                         printf("%4d ",a[i][j]);
    
51.                 }
    
52.                 printf("\n");
    
53.         }
    
54.         return 0;
    
55. }

复制代码

我是按洛谷上的要求写的，用的是递归大法，比较好写一些，目测数学也可以做

zhwang

刚刚搞那道变形的最小生成树RE一个点差点没把我杀了，拖久了。

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,ax,ay;
   
4. const int mx=5010;
   
5. int a[mx][mx],i,k;
   
6. int left_,right_,on_,under_;
   
7. int main()
   
8. {
   
9.     cin>>n>>ax>>ay;
   
10.     left_=1,right_=n,on_=1,under_=n,k=0;
    
11.     while (k<=n*n-1)
    
12.     {
    
13.         for (i=left_; i<=right_; i++)
    
14.         {
    
15.             k++;
    
16.             a[on_][i]=k;
    
17.         }
    
18.         on_++;///向下挪一格
    
19.         for (i=on_;i<=under_;i++)
    
20.         {
    
21.             k++;
    
22.             a[i][right_]=k;
    
23.         }
    
24.         right_--;///向左挪一格
    
25.         for (i=right_;i>=left_;i--)
    
26.         {
    
27.             k++;
    
28.             a[under_][i]=k;
    
29.         }
    
30.         under_--;///向上挪一格
    
31.         for (i=under_;i>=on_;i--)
    
32.         {
    
33.             k++;
    
34.             a[i][left_]=k;
    
35.         }
    
36.         left_++;
    
37.     }
    
38.     /*
    
39.     for (i=1;i<=n;i++)
    
40.     {
    
41.         for (int j=1;j<=n;j++)
    
42.             cout<<a[i][j]<<" ";
    
43.         cout<<endl;
    
44.     }
    
45.     */
    
46.     cout<<a[ax][ay];
    
47.     return 0;
    
48. }
    

复制代码

张笑宇

尴尬为什么RE了5个点？？？

zhwang

张笑宇 发表于 2018-7-31 09:33
尴尬为什么RE了5个点？？？

洛谷上是30000*30000，是要分层处理的，模拟不够

张笑宇

zhwang 发表于 2018-7-31 10:33
洛谷上是30000*30000，是要分层处理的，模拟不够

谢谢大佬知道了

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,x,y,all=0;
    
14. int main()
    
15. {
    
16.         scanf("%d%d%d",&n,&x,&y);
    
17.         int cen=min(min(x,n-x+1),min(y,n-y+1));
    
18.         for(int i=1;i<=cen-1;i++)
    
19.                 all+=(n-i*2+1)*4;
    
20.         if(cen==x)
    
21.                 printf("%d ",all+y-cen+1);
    
22.         else if(cen==(n-y+1))
    
23.                  printf("%d ",all+n-(cen-1)*2+x-cen);
    
24.         else if(cen==y)
    
25.                 printf("%d ",all+(n-(cen-1)*2)*3+n-cen-x-1);
    
26.         else
    
27.                 printf("%d ",all+(n-(cen-1)*2)*2+n-cen-y);
    
28.         return 0;
    
29. }

复制代码

admin

上完整的程序，使用代码模式

admin

你们做的都是在什么题呀？