Tìm đường đi có trọng số nhỏ nhất

[Wipad]

Trò chơi được cho bởi một bảng gồm m hàng và n cột, các hàng được đánh số từ 1 đến m (từ trên xuống), các cột được đánh số từ 1 đến n (từ trái sang phải). Ô nằm giao giữa hàng i và cột j là ô (i, j). Mỗi ô được tô một màu có mã màu là một ký tự thuộc tập ['A', 'B', ..., 'Z'], các ô chứa món quà tô màu có mã màu là ký tự *. Nhiệm vụ của người chơi là: xuất phát từ một ô (x, y) cần tìm đường đi tới một ô chứa món quà theo quy tắc di chuyển như sau:

• Chỉ di chuyển sang các ô chung cạnh;
• Nếu di chuyển sang ô mới cùng màu với ô hiện tại thì không mất chi phí di chuyển, còn nếu di chuyển sang ô mới khác màu với ô hiện tại thì mất chi phí là 1.

Yêu cầu: Cho bảng ký tự biểu diễn trò chơi và ô (x, y), hãy tính chi phí di chuyển ít nhất của đường đi từ ô (x, y) đến một ô ký tự *.
Dữ liệu:

• Dòng đầu chứa ba số nguyên dương m, n, Q;
• m dòng tiếp theo, mỗi dòng chứa một xâu độ dài n mô tả bảng ký tự là mã màu của các ô;
• Q dòng tiếp theo, mỗi dòng chúa hai số nguyên x, y.

Kết quả:
Gồm Q dòng, mỗi dòng ghi một số nguyên là chi phí di chuyển ít nhất của đường đi từ ô (x, y) đến một ô chứa ký tự *.
Ràng buộc:

• Có 40% số test tương ứng với 40% số điểm thỏa mãn điều thỏa mãn điều kiện m, n <= 10^2; Q = 1;
• Có 40% số test khác tương ứng với 40% số điểm thỏa mãn điều kiện m, n <= 10^3, Q <= 3;
• Có 20% số test khác tương ứng với 20% số điểm còn lại có m, n <= 10^3 ; Q <= m x n.

Ví dụ:

• Input

*ADFEB
AD*CFB
ACBADA
AAAAAA
3 6
1 6
1 5

• Output

1
2
3

Chào mọi người, đến dịp sắp thi học sinh giỏi em lại ngoi lên tìm kiếm sự giúp đỡ ^_^, bài này em làm theo Dijkstra thì bị quá thời gian mất nửa bộ test, em đang tính đến dùng thuật Floyd, nhưng mà vẫn chưa định hình được cách làm, nhờ mọi người giúp đỡ. Em cảm ơn!!!

[noname00 (HK boy)]

@Wipad

Dijkstra thì bị quá thời gian mất nửa bộ test, em đang tính đến dùng thuật Floyd

Dijkstra mất O(V+E\log V) (chưa tính nhân thêm Q query) mà bạn còn bị TLE, Floyd O(V^3) liệu có chạy được trong time limit không?

Bạn làm Dijkstra như thế nào? Code của bạn đâu?

[Wipad]

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<string>
#define ll long long
#define st first
#define nd second
#define IOS ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1E3 + 5;
const int oo = 2E9 + 7;

int dx[] = {-1, 1, 0, 0},
	dy[] = {0, 0, 1, -1},
	d[N][N];
int m, n, Q;
char s[N][N];
vector<pair<int, int>> a;

void input() {
	cin >> m >> n >> Q;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j) {
			cin >> s[i][j];
			if (s[i][j] == '*')
				a.push_back({i, j});
		}
}

void BFS(int i, int j) {
	d[i][j] = 0;
	queue<pair<int, int>> q;
	q.push({i, j});
	while(!q.empty()) {
		int u = q.front().st,
			v = q.front().nd;
		q.pop();
		
		for(int k = 0; k <= 3; ++k) {
			int x = u + dx[k],
				y = v + dy[k];
			if (x >= 1 && x <= m & y >= 1 && y <= n) {
				if (s[x][y] != s[u][v]) {
					if (d[x][y] > d[u][v] + 1) {
						d[x][y] = d[u][v] + 1;
						if (s[x][y] != '*') 
							q.push({x, y});
					}
				}
				else if (s[x][y] == s[u][v]) {
					if (d[x][y] > d[u][v]) {
						d[x][y] = d[u][v];
						if (s[x][y] != '*')
							q.push({x, y});
					}
				}
			}
		}
	}
}

void Query() {
	int x, y;
	int res = oo;
	while (Q--) {
		res = oo;
		memset(d, 0x3f, sizeof(d));
		cin >> x >> y;
		BFS(x, y);
		for (pair<int, int> u: a)
			res = min(res, d[u.st][u.nd]);
		cout << res << "\n";	
	}
}

int main () {
	IOS
	input();
	Query();
	return 0;
}

Code của em đây
Nhờ mọi người xem giúp em ạ!

@noname00

Dijkstra mất O(V+E\log⁡V) (chưa tính nhân thêm Q query) mà bạn còn bị TLE, Floyd O(V^3) liệu có chạy được trong time limit không?

À cái em có nhẫm lẫn chút @@. Cảm ơn anh

[noname00 (HK boy)]

Thực ra bài này dễ nhất là bạn làm ngược lại đề bài bảo.

Đề bài bảo tính quãng đường ngắn nhất từ ô (x, y) đến 1 ô * bất kỳ, vậy bây giờ bạn sẽ tính khoảng cách ngắn nhất từ 1 ô * bất kỳ đến 1 ô (x, y) cho trước. Mà đường đi ngắn nhất chính là tính từ BFS.

Bạn nhét tất cả vị trí các ô * vào queue và làm BFS bình thường.

[Wipad]

Chỉ thay đổi một chút về ý tưởng mà đúng hết bộ test rồi anh. Cảm ơn anh nhiều!