[数据结构与算法]马踏棋盘栈实现C语言

马踏棋盘栈实现C语言

# include <stdio.h>
# include <stdlib.h>

# define ROW 4
# define COL 4

int board[ROW][COL] = {0};
int size = 0;
int dirRow[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dirCol[] = {-2, -1, 1, 2, 2, 1, -1, -2};

typedef struct Node {
	int row;
	int col;
	int way;
	struct Node* next;
} Node;

Node* _new(int row, int col) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->row = row;
	node->col = col;
	node->way = 0;
	node->next = NULL;
	return node;
}

void push(Node* stack, int row, int col) {
	Node* node = _new(row, col);
	node->next = stack->next;
	stack->next = node;
	size++;
}

void pop(Node* stack) {
	Node* node = stack->next;
	stack->next = node->next;
	free(node);
	size--;
}

Node* peek(Node* stack) {
	return stack->next;
}

int isPass(int row, int col) {
	if (row >= 0 && row < ROW && col >= 0 && col < COL && board[row][col] == 0) {
		return 1;
	}
	return 0;
}

void house(int startRow, int startCol) {
	Node *stack = _new(0, 0);
	push(stack, startRow, startCol);
	board[startRow][startCol] = size;
	while (size < ROW * COL) {
		Node* cur = peek(stack);
		if (cur->way < 8) {
			int row = cur->row + dirCol[cur->way];
			int col = cur->col + dirRow[cur->way];
			if (isPass(row, col)) {
				push(stack, row, col);
				board[row][col] = size;
			}
			cur->way++;
		} else {
			board[cur->row][cur->col] = 0;
			pop(stack);
		}
	}
}

void board2() {
	int i, j;
	for (i = 0; i < ROW; i++) {
		for (j = 0; j < COL; j++) {
			printf("%2d ", board[i][j]);
		}
		if (i != ROW - 1) {
			printf("\n");
		}
	}
}

int main() {
	int row, col;
	scanf("%d%d", &row, &col);
	house(row - 1, col - 1);
	board2();
	return 0;
}