BFS 解决蛇形填数

题目描述是经典的蛇形填数问题。

以前解决这类问题，通常是通过控制$i,j$的值来定位数组元素的位置，然后进行赋值。但是这种方法非常的繁琐，且难于理解。容易出错。

今天在做这道题目的时候，通过搜索资料，思索出了一种新解法，相较于原来的解法更以理解，且时间复杂度更低。解法的基本思想是 BFS。下面我们仔细来探讨一下。

首先我们定义一组偏移量数组：

1
2
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, -1, 0, 1 };

这个数组的顺序必须和填数的顺序一致。在这里，它被定义为逆时针填数。

然后我们需要设置 BFS 的起点：

1
2
x = 1; y = N; i = 0;
f[x][y] = nNum++;

其中，$x,y$用来保存当前坐标，$i$则是保存当前偏移量的数组下标。$f\left [ x \right ]\left [ y \right ]$表示需要填充的矩阵，$nNum$则是所需要填的数。

我们来简单的模拟以下，假设现在坐标为$\left ( 1,n \right )$，偏移量下标$i=0$。首先尝试向右扩展标$\left ( 1,n+1 \right )$，不合法，于是返回到坐标$\left ( 1,n \right )$再先下扩展，检测合法后，进行填充，当填充到最下端时，又不合法，这样，返回到坐标$\left ( n,n \right )$后向左扩展，同理，填充到最左端后又会向上扩展，这里还需要检测当前扩展结点是否已经填数。如果已经填数，则不合法，需要返回上一个坐标。

这样我们模拟一遍 BFS 就可以知道，这种解法是正确的，所以这里略过证明。

基本代码如下：

 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
#include <iostream>
#include <memory.h>

using namespace std;

const int MAX = 16;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, -1, 0, 1 };

int x, y, i, nNum = 1;
int N, f[MAX][MAX];

int main()
{
    memset(f, 0, sizeof(f));
    cin >> N;
    x = 1; y = N; i = 0;
    f[x][y] = nNum++;
    while(nNum <= N * N)
    {
        x += dx[i]; y += dy[i];
        if(x >= 1 && x <= N && y >= 1 && y <= N && f[x][y] == 0)
        { f[x][y] = nNum++; }
        else
        {
            x -= dx[i]; y -= dy[i];
            i = (i + 1) % 4;
        }
    }
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(N * N > 99 && f[i][j] < 100) { cout << " "; }
            if(N * N > 9 && f[i][j] < 10) { cout << " "; }
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

BFS 解决蛇形填数 - NOIP1995P2

本文介绍了使用BFS（广度优先搜索）解决经典的蛇形填数问题，提供了相较于传统方法更易理解且时间复杂度更低的解法。