Q291: The House Of Santa Claus

/*
    利用DFS去做
    Run time: 0.000
*/
#include <stdio.h>
const int N = 5;
int arr[N][N] = {
                    {0,1,1,0,1},
                    {1,0,1,0,1},
                    {1,1,0,1,1},
                    {0,0,1,0,1},
                    {1,1,1,1,0}
                };
int record[9];

void DFS(int count, int index);

int main()
{
    int count = 8;
    DFS(count, 0);

}

void DFS(int count, int index)
{
    static int m;  // to record the node index
    int i, j, k;

    if (count == 0)
    {
        record[m] = index+1;  // record the node

        for ( k = 0; k < 9; k++)
            printf("%d", record[k]);
        printf("\n");

        return;
    }

    else
    {
        for ( i = 0; i < N; i++)
        {
            if (arr[index][i])
            {
                arr[index][i] = 0;  // line delete
                arr[i][index] = 0;  // line delete

                // whether there is no line at line index or not
                for ( j = 0; j < N; j++)
                    if (arr[i][j])
                        break;

                // if there is no line at line index
                if (j == N && count-1)
                {
                    arr[index][i] = 1;
                    arr[i][index] = 1;
                    continue;
                }

                count--;  // line number delete
                record[m++] = index+1;  // record the node

                DFS(count, i);  // recursive call

                arr[index][i] = 1;  // line recovery
                arr[i][index] = 1;  // line recovery
                count++;  // line number recovery
                m--;
            }
        }
    }

}