SPOJ.COM - Thuật toán bài SERGRID - Grid

Đề bài:

Bạn đang ở trên một cái lưới nxm nơi mà mỗi ô vuông trên lưới đó có một số trên đó. Từ một ô cho trước trên lưới có một số có giá trị k. Một lần di chuyển bao gồm chính xác k ô vuông theo 4 hướng chính. Biết bạn không thể nhảy ra khỏi lưới. Hỏi số bước nhỏ nhất để di chuyển từ ô vuông trên cùng bên trái đến ô vuông dưới cùng bên phải là bao nhiêu.

Đầu vào

Mỗi đầu vào sẽ bao gồm một test case duy nhất. Chú ý rằng chương trình của bạn có thể được chạy nhiều lần trên những đầu vào khác nhau. Dòng đầu tiên của đầu vào bao gồm 2 số nguyên n và m được ngăn cách bởi dấu cách (1 <= n, m <= 500), biểu thị kích thước của lưới. Đảm bảo rằng ít nhất một cạnh của lưới (tức n hoặc m) sẽ lớn hơn 1. n dòng tiếp theo, mỗi dòng chứa m chữ số và không có dấu cách, biểu thị ma trận nxm. Mỗi chữ số có giá trị từ 0 đến 9 (bao gồm cả 2 chữ số đó). Ô vuông trên cùng bên trái của lưới tương ứng với kí tự đầu tiên, của dòng đầu tiên, của mỗi test case. Ô vuông dưới cùng bên phải tương ứng với kí tự cuối cùng, của dòng cuối cùng, của mỗi test case.

Đầu ra

In ra duy nhất trên 1 dòng một số - biểu diễn giá trị là số bước nhỏ nhất để di chuyển từ góc trên cùng bên trái xuống góc dưới cùng bên phải. Nếu không thì in ra -1.

Ví dụ

Đầu vào:

5 4 
2120 
1203 
3113 
1120 
1110

Đầu ra:

6

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/SERGRID/

Phân tích

Đây là bài toán cơ bản áp dụng thuật toán tìm kiếm theo chiều rộng BFS. Mình sẽ bắt đầu từ điểm đầu tiên là điểm trên cùng bên trái. Rồi đi tới các điểm kề với nó theo 4 hướng với quy tắc là số bước nhảy đúng bằng giá trị của ô đang xét hiện tại.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

const int MAX = 505;
const int MAX_QUEUE = MAX*MAX;

int n, m;               // Kích thước ma trận
int Matrix[MAX][MAX];   // Ma trận ban đầu
int Mark[MAX][MAX];     // Ma trận đánh dấu

typedef struct
{
	int row;
	int col;
}Point;

// Hàng đợi vòng
Point queue[MAX_QUEUE];
int fr, re, leng;

void Enqueue(int row, int col)
{
	Point p;
	p.row = row;
	p.col = col;

	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr =  (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

int drow[] = {-1,0,1, 0};
int dcol[] = { 0,1,0,-1};

/*
* Thuật toán BFS từ điểm đầu tiên (sr, sc)
*/
void BFS(int sr, int sc)
{
	fr = re = leng = 0;
	Mark[sr][sc] = 1;
	Enqueue(sr,sc);

	while(leng > 0)
	{
		Point p = Dequeue();
		for(int i = 0; i < 4; i++)
		{
			int r = p.row + (drow[i]) * Matrix[p.row][p.col];
			int c = p.col + (dcol[i]) * Matrix[p.row][p.col];
			if( r >= 0 && r < n && c >= 0 && c < m &&
			    (Mark[r][c] == 0 || Mark[r][c] > Mark[p.row][p.col] + 1)
			    )
			{
				Mark[r][c] = Mark[p.row][p.col] + 1;
				Enqueue(r,c);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		char tmp[MAX];
		cin >> tmp;
		for(int j = 0; j < m; j++)
		{
			Matrix[i][j] = tmp[j] - '0';
			Mark[i][j]   = 0;
		}
	}

	BFS(0,0);

	// Nếu giá trị ô cuối cùng vẫn bằng 0, nghĩa là nó được thăm
	if(Mark[n-1][m-1] == 0) cout << -1 << endl;
	else cout << Mark[n-1][m-1] - 1 << endl;
	return 0;
}