Каков порядок следующего алгоритма?

Question

Ниже приведен простой алгоритм, который я написал для рекурсивного посещения всех соседей ячейки в сетке:

#include <stdio.h>
#include <string.h>

#define N 2

// Tracks number of times a cell has been visited.
static int visited[N][N];
// If 1, means a cell has already been visited in the current path
// through the grid.
static int been[N][N];

void visit(int x, int y, int level)
{
    int i;
    int j;
    visited[x][y] += 1;
    been[x][y] = 1;
    for (i = -1; i < 2; i++)
        for (j = -1; j < 2; j++) 
        {
            // Neighbor has to be in the grid and not already visited
            // in the current path to be visited.
            if (x + i > -1 && x + i < N && y + j > -1 && y + j < N)
            {
                if (been[x + i][y + j] != 1)
                {
                    visit(x + i, y + j, level + 1);
                }
            }
        }
    been[x][y] = 0;
}

void main(void)
{
    int x;
    int y;
    int total;
    // Initialization.
    for (x = 0; x < N; x++)
        for (y = 0; y < N; y++) 
        {
            visited[x][y] = 0;
            been[x][y] = 0;
        }
    // Algorithm.
    for (x = 0; x < N; x++)
        for (y = 0; y < N; y++)
        {
            visit(x, y, 0);
        }
    // Print results.
    total = 0;
    for (x = 0; x < N; x++)
        for (y = 0; y < N; y++)
        {
            printf("x: %d, y: %d, visited: %d\n", x, y, visited[x][y]);
            total += visited[x][y];
        }
    printf("N: %d, total: %d\n", N, total);
}

Мне любопытно, как устроен этот алгоритм. Когда я запускаю его с N = 2, вывод:

x: 0, y: 0, visited: 16
x: 0, y: 1, visited: 16
x: 1, y: 0, visited: 16
x: 1, y: 1, visited: 16
N: 2, total: 64

Когда я запускаю его с N = 3, я получаю:

x: 0, y: 0, visited: 1373
x: 0, y: 1, visited: 1037
x: 0, y: 2, visited: 1373
x: 1, y: 0, visited: 1037
x: 1, y: 1, visited: 665
x: 1, y: 2, visited: 1037
x: 2, y: 0, visited: 1373
x: 2, y: 1, visited: 1037
x: 2, y: 2, visited: 1373
N: 3, total: 10305

Я был удивлен, увидев, что середина сетки 3х3 посещена наименьшее количество раз, а углы - больше всего. Я думал, что углы будут посещены меньше всего, потому что у них есть только 3 соседа, в то время как у середины сетки есть 8.

Мысли

Answer 1

В сетке 3х3 много путей.

• Большинство путей заканчиваются на углах (для этого нужно посетить только 3 клетки).
• Затем некоторые заканчиваются по краям (для посещения требуется 5 ячеек).
• В центре очень мало путей, которые заканчиваются (им требуется посещение всех 8 окружающих ячеек).

Два пути, которые являются общими для ячейки, только увеличивают ваш счетчик посещений для этих ячеек один раз.Например, пути ABCD и ABCE увеличивают A, B и C только один раз.Ваш код на самом деле не считает посещения по разным путям - для этого вам нужно заменить

void visit(int x, int y, int level) {
   ...
   visited[x][y] += 1;
   ...
      visit(x + i, y + j, level + 1);
   ...
}

на

int visit(int x, int y, int level) {
   ...
   int child_paths = 1; // do not increment visited[x][y] yet
   ...
      child_paths += visit(x + i, y + j, level + 1);
   ...
   visited[x][y] += child_paths;
   return child_paths;
}