Thuật toán của game Lines98 (P.2)

Phần 2. Tìm đường đi ngắn nhất

Khi người chơi chọn 1 viên bi ở vị trí (i1, j1) và chọn tiếp 1 ô trống ở vị trí (i2, j2). Ta cần di chuyển viên bi đó từ (i1, j1) đến (i2, j2) nếu có đường đi (phải là ngắn nhất), hoặc nếu không có đường đi thì phát ra âm thanh thông báo.

Đường đi là 1 dãy liên tiếp các ô trống (trừ ô đầu tiên ko cần trống, dĩ nhiên) kề cạnh nhau. Chú ý: 2 ô kề cạnh tức là chúng có chung 1 cạnh (nôm na là nằm sát nhau), trường hợp 2 ô chỉ chung đỉnh (nằm chéo nhau) thì ko được tính là kề cạnh.

Sử dụng Tìm kiếm theo chiều rộng (Breadth First Search – BFS) trong Lý thuyết đồ thị. Xây dựng đồ thị G như sau:

  • Tập đỉnh V: là 91 ô của bảng, mỗi ô đóng vai trò là 1 đỉnh.
  • Tập cạnh E: 2 ô kề cạnh nhau và đều trống thì giữa chúng có cạnh nối, coi như ô (i1, j1) là trống.

Chạy BFS cho G, với đỉnh bắt đầu là (i2, j2) và đỉnh kết thúc là (i1, j1). Làm ngược như vậy là vì như ta đã biết, sau khi chạy BFS xong, lúc truy hồi đường đi, ta có đường đi ngược. Nên nếu tìm đường đi từ (i2, j2) đến (i1, j1) thì tiện lợi hơn vì cuối cùng ta có đường đi thuận (ngược của ngược thì thành thuận).

Mã giả:

- Tạo 1 queue đủ lớn.
- Đưa ô (i2 ,j2) vào queue.
- Lặp lại các việc sau khi queue chưa cạn:
{
	+ Lấy ra 1 ô trong queue: (x, y).
	+ Xét 4 ô xung quanh ô (x, y) ví dụ (p, q):
	{
		Nếu (p, q) nằm trong bảng và (p, q) trống thì:
		{
			Thêm (p, q) vào queue.
			Ghi nhận (đánh dấu) ô (x, y) là ô đi trước ô (p, q).
			Nếu (p, q) chính là (i1, j1) thì chấm dứt vòng lặp.
		}
	}
}
- Nếu ô (i1, j1) chưa được đánh dấu thì kết luận ko có đường đi.
- Nếu ô (i1, j1) đã được đánh dấu thì truy hồi đường đi.

Mã thật – C:

typedef struct
{
	int x;
	int y;
} Point;

typedef struct
{
	int len;
	Point point[BOARD_COL * BOARD_ROW];
} PointList;

PointList findPath(int** a, int i1, int j1, int i2, int j2)
{
	int dadi[BOARD_COL][BOARD_ROW];
	int dadj[BOARD_COL][BOARD_ROW];

	int queuei[BOARD_COL * BOARD_ROW];
	int queuej[BOARD_COL * BOARD_ROW];

	int u[] = {1, 0, -1, 0};
	int v[] = {0, 1, 0, -1};

	int fist = 0, last = 0;

	int x, y, xx, yy, i, j, k;

	PointList res;
	res.len = 0;

	for (x = 0; x < BOARD_COL; x++)
		for (y = 0; y <; BOARD_ROW; y++)
			dadi[x][y] = -1;

	queuei[0] = i2;
	queuej[0] = j2;
	dadi[i2][j2] = -2;

	while (fist <= last)
	{
		x = queuei[fist];
		y = queuej[fist];
		fist++;
		for (k = 0; k < 4; k++)
		{
			xx = x + u[k];
			yy = y + v[k];
			if (xx == i1 && yy == j1)
			{
				dadi[i1][j1] = x;
				dadj[i1][j1] = y;

				i = 0;
				while (1)
				{
					res.point[i].x = i1;
					res.point[i].y = j1;
					i++;
					k = i1;
					i1 = dadi[i1][j1];
					if (i1 == -2) break;
					j1 = dadj[k][j1];
				}
				res.len = i;
				return res;
			}

			if (!isInside(xx, yy)) continue;

			if (dadi[xx][yy] == -1 && a[xx][yy] <= 0)
			{
				last++;
				queuei[last] = xx;
				queuej[last] = yy;
				dadi[xx][yy] = x;
				dadj[xx][yy] = y;
			}
		}
	}

	return res;
}

int isInside(int i, int j)
{
	return (i >= 0 && i < BOARD_COL && j >= 0 && j < BOARD_ROW);
}

Còn nữa…

Advertisements

5 thoughts on “Thuật toán của game Lines98 (P.2)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s