SPOJ.COM - Thuật toán bài SHOP - Shopping

Đề bài:

Màn hình ống cũ máy tính của bạn hóa ra là nguyên nhân gây ra đau đầu mãn tính của bạn. Do đó bạn quyết định mua một trong những màn hình TFT phẳng mới. Tại lối vào của cửa hàng máy tính, bạn thấy rằng có khá đông đủ khách hàng.

(Câu tiếp theo mình không hiểu lắm. Tuy nhiên nó không quan trọng, nên mình sẽ bỏ qua. Nếu bạn hiểu câu này nói gì, vui lòng viết dưới phần bình luận để mọi người cùng hiểu nhé.) Bởi vì, bạn muốn về nhà sớm để hoàn thành công việc còn dang dở ở trên SPOJ; nên bạn muốn lé tránh đám đông được nhiều nhất có thể. Bạn xem xét tình hình ở một vài nơi và nhận ra rằng đám đông là ít hơn ở một vài chỗ ở cửa hàng. Đó là lí do cho bạn để hy vọng rằng bạn sẽ đến đích đúng giờ, với quãng đường đi ngắn nhất. Nhưng đường đi ngắn nhất là đường nào?

Bạn phác họa tình hình trên một miếng giấy. Tuy nhiên nó vẫn là một vấn đề khó. Bạn lấy ra một cuốn sổ trong túi và viết một chương trình để tìm đường đi ngắn nhất cho bạn.

Đầu vào

Dòng đầu tiên của đầu vào miêu tả chiều rộng w và chiều dài h của cửa hàng. Cả hai chiều đều không vượt quá 25. h dòng tiếp theo, mỗi dòng chứa w kí tự. Trong đó, kí tự 'S' miêu tả cái giá, kí tự 'S' là vị trí bắt đầu và kí tự 'D' là đích đến (ví dụ là một hình vuông phía trước những màn hình). Tất cả những khối hình vuông trống được đánh số từ 1 đến 9 - là số giây cần để vượt qua khu vực hình vuông đó.

Có rất nhiều test case và được ngăn cách nhau bởi dòng trống. Đầu vào kết thúc bởi giá trị độ rộng và chiều dài là 0 0.

Đầu ra

Với mỗi test case, in ra giá trị số giây nhỏ nhất để đi được tới đích. Mỗi test case in ra trên một dòng riêng biệt. Bạn có thể di chuyển theo chiều ngang hay chiều dọc. Dĩ nhiên, bạn phải di chuyển bên trong của ma trận. Và luôn có đường để tới đích.

Ví dụ

Đầu vào:

4 3
X1S3
42X4
X1D2

5 5
S5213
2X2X5
51248
4X4X2
1445D

0 0

Đầu ra:

4
23

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

Phân tích

Đây là bài toán tìm đường đi ngắn nhất cơ bản trên ma trận. Nó tương đương với bài toán tìm đường đi ngắn nhất của đồ thị có trọng số (vì các đường đi có giá khác nhau). Vì vậy, mình sử dụng thuật toán Dijkstra để giải quyết bài toán.

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_INT = 1<<20;
const int MAX = 30;

int w, h;               // Kích thước ma trận
int SR, SC, DR, DC;     // Lần lượt là hàng, cột của điểm bắt đầu, kết thúc
int number;             // Số lượng điểm mà bạn có thể đi vào
int Matrix[MAX][MAX];   // Ma trận đầu vào
int Distance[MAX][MAX]; // Ma trận khoảng cách sau khi áp dụng Dijkstra
bool Mark[MAX][MAX];    // Ma trận đánh dấu

/*
* Tìm điểm chưa thăm, có thể đi và giá trị ma trận khoảng cách là nhỏ nhất
* Tham số dạng tham chiếu để lưu tọa độ hàng, cột tìm được
*/
void FindMin(int &rmin, int &cmin)
{
	int _min = MAX_INT;
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			if(Mark[i][j] == false && Matrix[i][j] != -1 && Distance[i][j] < _min)
			{
				_min = Distance[i][j];
				rmin = i;
				cmin = j;
			}
}

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

/*
* Thuật toán Dijkstra tại điểm bắt đầu là (sr, sc)
*/
void Dijkstra(int sr, int sc)
{
    // Đếm số điểm đã xét, khi duyệt hết các điểm có thể thì dừng
	int cnt = 0;
	Distance[sr][sc] = 0;
	while (cnt < number)
	{
		int rmin = 0, cmin = 0;
		FindMin(rmin,cmin);

		Mark[rmin][cmin] = true;
		cnt++;
		for(int i = 0; i < 4; i++)
		{
			int r = rmin + drow[i];
			int c = cmin + dcol[i];
			if( r >= 0 && r < h && c >= 0 && c < w &&
			    Mark[r][c] == false && Matrix[r][c] != -1 &&
			    Distance[rmin][cmin] + Matrix[r][c] < Distance[r][c]
			    )
				Distance[r][c] = Distance[rmin][cmin] + Matrix[r][c];
		}
	}
}

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

	while(true)
	{
		cin >> w >> h;
		if(w==0 && h==0) break;

		SR = SC = DR = DC = number = 0;
		for(int i = 0; i < h; i++)
		{
			char temp[MAX];
			cin >> temp;
			for(int j = 0; j < w; j++)
			{
				if(temp[j]=='X')
				{
					Matrix[i][j] = -1;
					number++;
				}
				else if(temp[j]=='S')
				{
					Matrix[i][j] = 0;
					SR = i;
					SC = j;
				}
				else if(temp[j]=='D')
				{
					Matrix[i][j] = 0;
					DR = i;
					DC = j;
				}
				else Matrix[i][j] = temp[j] - '0';
				Distance[i][j] = MAX_INT;
				Mark[i][j] = false;
			}
		}
		number = w*h - number;
		Dijkstra(SR,SC);
		cout << Distance[DR][DC] << endl;
	}
	return 0;
}