[原创]HRBUST 1564 螺旋矩阵 DFS

2016-03-03 13:19:37 Tabris_ 阅读数：553

博客爬取于2020-06-14 22:45:04
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50787788

HRBUST 1564 螺旋矩阵 DFS

点击此处一大神的本题题解

螺旋矩阵
Time Limit: 1000 MS Memory Limit: 10240 K
Total Submit: 282(78 users) Total Accepted: 81(72 users) Rating: Special Judge: No
Description
对于给定的一个数n，要你打印n*n的螺旋矩阵。

比如n=3时，输出：

1 2 3
8 9 4
7 6 5

Input
多组测试数据，每个测试数据包含一个整数n（1<=n<=32）
Output
对于每组测试数据，输出一个n*n的螺旋矩阵，定义在题目描述里。

在一组测试数据中，每个数占的字符宽度是该组数据中最大的数位数加1，比如3*3的螺旋矩阵，最大值是9，那么每个数就要占2个字符宽度。

两组测试数据之间用一个空行隔开。

Sample Input
1
2
3
Sample Output
1

1 2
4 3

1 2 3
8 9 4
7 6 5

本题我用的是搜索
关键点在于搜索的方向控制
方向控制很简单 就是用fx[4]与fy[4]控制方向
“→”“↓”“←”“↑”这四个方向的循环
如果上一次搜索是那个搜索那个方向的 如果搜索的图已经到头了
就从下一个方向开始搜索
如下就是搜索的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x,int y,int ii)
{
    int xx,yy;
    for(int i=ii;i<4+ii;i++)
    {
        xx=x+fx[i%4];
        yy=y+fy[i%4];
        if(xx>0&&yy>0&&xx<=n&&yy<=n&&a[xx][yy]==0)
        {
            a[xx][yy]=num++;
           // printf("%d %d  -%d\n",xx,yy,a[xx][yy]);
            dfs(xx,yy,i%4);
            num--;
        }
    }
}

本题非常容易PE 主要由以下两点
1.两组数据中间的空格。（这个很容易 但是要读题啊 博主就因为没看到而PE多次）
2.图内最大的数有几位 图内的所有数都占几+1位（这样想就没有空格的干扰了）
关于控制数据占位的个数可以这样表示

1
printf("%*d",length+1,a[i][j]); //其中*号是位数 对应length是对应位数的数据 +1是数值之前的空格占一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <iostream>
# include <stdio.h>
# include <vector>
# include <stdio.h>
# include <queue>
# include <string.h>
# include <algorithm>
using namespace std;
int n,num;
int a[34][34];
int fx[4]={0,1,0,-1};
int fy[4]={1,0,-1,0};
void dfs(int x,int y,int ii)
{
    int xx,yy;
    for(int i=ii;i<4+ii;i++)
    {
        xx=x+fx[i%4];
        yy=y+fy[i%4];
        if(xx>0&&yy>0&&xx<=n&&yy<=n&&a[xx][yy]==0)
        {
            a[xx][yy]=num++;
           // printf("%d %d  -%d\n",xx,yy,a[xx][yy]);
            dfs(xx,yy,i%4);
            num--;
        }
    }

}
int main()
{
    int flag=0;
    while(~scanf("%d",&n))
    {
        if(flag==1) {printf("\n");}
        memset(a,0,sizeof(a));
        num=2;
        int length=1,m=n*n;
        while(m>=10)
        {
            length++;
            m/=10;
        }
        for(int i=0;i<=n+1;i++)
        {
            a[0][i]=999;
            a[i][0]=999;
            a[i][n+1]=999;
            a[n+1][i]=999;
        }
        a[1][1]=1;
        dfs(1,1,0);

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                printf("%*d",length+1,a[i][j]);
            }
            printf("\n");
        }
        flag=1;
    }
}