What's the order of the following algorithm?

Below is a simple algorithm that I wrote for recursively visiting all of a cell's neighbors in a grid:

#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 tota开发者_开发问答l;
    // 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);
}

I'm curious as to the order of this algorithm. When I run it with N = 2, the output is:

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

When I run it with N = 3, I get:

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

I was surprised to see the middle of the 3x3 grid visited the least number of times and the corners visited the most. I thought the corners would be visited the least because they have only have 3 neighbors while the middle of the grid has 8.

Thoughts?

There are many paths in a 3x3 grid.

• Most paths end at the corners (that only requires 3 cells to have been visited).
• Then some end at the edges (those require 5 cells to have been visited).
• There are very few paths that end at the center (they require all 8 surrounding cells to have been visited).

Two paths that are common up to a cell only increment your 'visited' counter for those cells once. For example, paths A-B-C-D and A-B-C-E increment A, B, and C only once. Your code does not really count visits in distinct paths - to do that, you would need to substitute

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

with

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;
}