LeetCode刷題總結（C語言版）_迷宮類

程式設計總結

每每刷完一道題後，其思想和精妙之處沒有地方記錄，本篇部落格用以記錄刷題過程中的遇到的演算法和技巧

#define DIRECT 4
#define MAX_N 128
static int **matrix;
static int m, n;
static int iGo[] = { -1, 0, 1, 0 };
static int jGo[] = { 0, 1, 0, -1 };
static int visited[MAX_N][MAX_N];

static bool IsValid(int i, int j)
{
	if (i < 0 || i >= m ||
		j < 0 || j >= n) {
		return false;
	}
	return true;
}

static bool IsNextOk(int i, int j, int direct)
{
	int nextI, nextJ;

	nextI = i + iGo[direct];
	nextJ = j + jGo[direct];

	if (!IsValid(nextI, nextJ)) {
		return true;
	}
	if (matrix[nextI][nextJ] == 1) {
		return true;
	}

	return false;
}

void GetNext(int i, int j, int direct, int *a, int *b)
{
	int nextI, nextJ;

	nextI = i + iGo[direct];
	nextJ = j + jGo[direct];

	while (IsValid(nextI, nextJ) && matrix[nextI][nextJ] == 0) {
		nextI = nextI + iGo[direct];
		nextJ = nextJ + jGo[direct];
	}
	*a = nextI - iGo[direct];
	*b = nextJ - jGo[direct];
}

static bool Dfs(int i, int j, int tarI, int tarJ, int direct)
{
	bool ret;
	int k;
	int nextI, nextJ;

	/* 到達終點了，並且在這個方向上有牆壁 */
	if (i == tarI && j == tarJ && IsNextOk(i, j, direct)) {
		return true;
	}

	if (IsValid(i, j) == 0) {  // 越界點
		return false;
	}

	if (matrix[i][j] == 1) {   // 牆壁
		return false;
	}

	if (visited[i][j] == 1) {  // 已經存取過
		return false;
	}

	visited[i][j] = 1;

	for (k = 0; k < DIRECT; k++) {
		GetNext(i, j, k, &nextI, &nextJ);  /* 走到這個方向最遠的地方 */
		ret = Dfs(nextI, nextJ, tarI, tarJ, k);
		if (ret) {
			return true;
		}
	}

	return false;
}

bool hasPath(int **maze, int mazeSize, int *mazeColSize, int *start, int startSize, int *destination, int destinationSize)
{
	int i, j;
	matrix = maze;
	m = mazeSize;
	n = *mazeColSize;
	memset(visited, 0, sizeof(visited));

	return Dfs(start[0], start[1], destination[0], destination[1], 0);
}

---

需要找到最短距離

#define DIRECT 4
#define MAX_QUEUE_SIZE 10001
#define MAX_N 128
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static int **g_matrix;
static int g_m, g_n;
static int g_iGo[] = {-1, 0, 1, 0};
static int g_jGo[] = {0, 1, 0, -1};
static int g_visited[MAX_N][MAX_N];

static bool IsValid(int i, int j)
{
	if (i < 0 || i >= g_m ||
		j < 0 || j >= g_n) {
		return false;
	}
	return true;
}

static int GetNext(int i, int j, int direct, int *a, int *b)
{
	int nextI, nextJ;
	int len = 0;

	nextI = i + g_iGo[direct];
	nextJ = j + g_jGo[direct];
	while (IsValid(nextI, nextJ) && g_matrix[nextI][nextJ] == 0) {
		nextI = nextI + g_iGo[direct];
		nextJ = nextJ + g_jGo[direct];        
		len++;
	}
	*a = nextI - g_iGo[direct];
	*b = nextJ - g_jGo[direct];
	return len;
} 

struct QNode {
	int i, j;
};

static struct QNode g_queue[MAX_QUEUE_SIZE];

static void Update(int *n)
{
	*n = (*n + 1) % MAX_QUEUE_SIZE;
}

static int Bfs(int i, int j, int tarI, int tarJ)
{
	int front, rear, curI, curJ, nextI, nextJ, k, len;

	front = 0;
	rear = 0;
	g_queue[rear].i = i;
	g_queue[rear].j = j;
	g_visited[i][j] = 0;
	Update(&rear);

	while (front != rear) {
		curI = g_queue[front].i;
		curJ = g_queue[front].j;
		Update(&front);

		for (k = 0; k < DIRECT; k++) {
			/* 走到這個方向最遠的地方 */
			len = GetNext(curI, curJ, k, &nextI, &nextJ);
			if (g_visited[nextI][nextJ] <= g_visited[curI][curJ] + len) {
				continue;
			}
			g_queue[rear].i = nextI;
			g_queue[rear].j = nextJ;
			g_visited[nextI][nextJ] = g_visited[curI][curJ] + len;
			Update(&rear);
		}
	}
	return g_visited[tarI][tarJ] == INT_MAX ? -1 : g_visited[tarI][tarJ];
}

int shortestDistance(int** maze, int mazeSize, int* mazeColSize, 
					 int* start, int startSize, int* destination, int destinationSize){
	int i, j;

	g_matrix = maze;
	g_m = mazeSize;
	g_n = *mazeColSize;

	for (i = 0; i < MAX_N; i++) {
		for (j = 0; j < MAX_N; j++) {
			g_visited[i][j] = INT_MAX;
		}
	}

	return Bfs(start[0], start[1], destination[0], destination[1]);
}

---------------------------------------
![在這裏插入圖片描述](https://img-blog.csdnimg.cn/20200812234956574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd3YW5nbW9vbl9saWdodA==,size_16,color_FFFFFF,t_70#pic_center)