Người dân ở đất nước B11 [láng giềng của đất nước C11] có một phong tục rất đặc biệt. Chuyện là họ rất thích hai chữ cái ‘A’ và ‘B’, cho nên bất kì ai đều được đặt tên chỉ gồm ‘A’ và ‘B’. Theo họ, một tên đẹp phải bao gồm tất cả các yếu tố sau:

• Tên phải không chứa quá countA chữ cái ‘A’
• Tên phải không chứa quá countB chữ cái ‘B’
• Mỗi xâu con gồm các chữ cái ‘A’ liên tiếp có độ dài không quá maxA
• Mỗi xâu con gồm các chữ cái ‘B’ liên tiếp có độ dài không quá maxB

Vào ngày Quốc khánh sắp tới, nhà vua đất nước B11 muốn tìm một tên đẹp dài nhất để đặt cho hoàng tử mới ra đời. Bạn hãy giúp nhà vua tính xem độ dài tên hoàng tử là bao nhiêu.

Ví dụ với countA = 3, countB = 5, maxA = maxB = 1, ta có tên đẹp dài nhất sẽ là ‘BABABAB’. Như vậy kết quả cần tìm là 7.

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: //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

using namespace std; const int MAX_INT = 1= 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