2 bài toán làm mình đau đầu, mọi người giúp gấp

[danghoaqt]

Bao vây

V­ương quốc Flatland có hình chữ nhật kích th­ước M x N ô vuông. V­uơng quốc được chia thành K tỉnh, mỗi tỉnh gồm 1 số ô vuông liên thông với nhau theo tiêu chuẩn kề cạnh. Không có điểm nào của Flatland là điểm biên của hơn 3 tỉnh, tức là không có đỉnh ô vuông nào là điểm chung của 4 tỉnh khác nhau.
Mỗi tỉnh được kí hiệu bằng 1 kí tự có mã ASCII lớn hơn 32. Thủ đô được kí hiệu là A và gồm đúng 1 ô. Thủ đô không phải là ô biên.
Vua của quốc gia thù địch Wrackland muốn thôn tính Flatland. Để làm được chuyện đó, ông ta phải chiếm được thủ đô của Flatland. Tuy vậy ông ta biết rằng quân đội của mình không đủ mạnh để chiếm hết các tỉnh của Flatland, để từ đó chiếm thủ đô. Vị vua độc ác này quyết định chiếm các tỉnh bao quanh thủ đô, vây hãm lâu dài thủ đô Flatland cho đến khi nước này phải đầu hàng.
Để làm được chuyện đó, quân đội Wrackland đánh chiếm một hoặc một số tỉnh biên giới của Flatland , từ đó chiếm tiếp các tỉnh kề với tỉnh đã chiếm được. Trên quan điểm quân sự, phải lên phương án hành động sao cho số tỉnh cần chiếm là ít nhất.
Yêu cầu: Xác định số tỉnh ít nhất mà vua Wrackland cần phải chiếm để vây hãm thủ đô Flatland hoặc cho biết là không thể làm được điều dú (nếu phải chiếm hết các tỉnh của Flatland ngoại trừ thủ đô).
Input: SIEGE.INP gồm nhiều bộ dữ liệu, mỗi bộ gồm 1 số dòng trong đó:
- Dòng đầu chứa 2 số nguyên M, N (3 <=M, N <=200)
- M dòng sau , mỗi dòng chứa N ký tự mã ASCII lớn hơn 32, mô tả các tỉnh của Flatland
- Kết thúc các bộ dữ liệu là dòng chứa 2 số 0 0
Output: SIEGE.OUT mỗi bộ dữ liệu đưa ra 1 số nguyên K tương ứng - số tỉnh ít nhẩ cần đánh chiếm; k=-1 nếu không có phương án
VD: SIEGE.INP
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
33333Z
3 3
BBB
BAB
BBB
0 0
OUT: SIEGE.OUT
4
-1

Ba thành phố

Trong một đất nước có N thành phố được đánh số từ 1 đến N. Có một số thành phố được nối với nhau bởi hệ thống các con đường cao tốc, mỗi con đường nối hai thành phố nào đó. Hệ thống đường cao tốc này có tính chất sau: Đối với hai thành phố bất kỳ A và B, nếu có cách di chuyển từ thành phố A đến thành phố B theo các con đường của hệ thống thì có đúng một cách di chuyển mà trong đó không có con đường nào bị đi qua quá 1 lần.
Tổng thống của dất nước này đặt ra câu hỏi sau đây đối với các nhà Tin học: Ba thành phố nào là cách xa nhau nhất. Chính xác hơn, ta gọi độ giãn cách giữa ba thành phố A, B và C là tổng số con đường cần sử dụng để di chuyển từ A đến B, tiếp đến di chuyển từ B đến C và cuối cùng di chuyển từ C đến A tuân thủ điều kiện: trong mỗi di chuyển vừa nêu, mỗi con đường chỉ được đi qua không quá 1 lần.
Yêu cầu: Tìm ba thành phố mà độ giãn cách giữa chúng là lớn nhất.
Dữ liệu vào : từ file văn bản COUNTRY.INP
- Dòng đầu tiên chứa số nguyên N (3 <=N <=1000)
- Tiếp theo là N dòng mô tả thông tin về các thành phố. Dòng thứ i chứa các số : Ki là số lượng thành phố có con đường nối với thành phố i (1 <=Ki<N), sau đó là Ki số nguyên là các chỉ số của các thành phố này.
Kết quả: ghi ra file văn bản COUNTRY.OUT: một số nguyên là độ giãn cách giữa ba thành phố tìm được
Ví dụ:
INP: 5
1 3
1 3
3 1 2 4
2 3 5
1 4
OUT: 8

[kevinsorbo]

em chẳng đọc đc gì cả . Bị làm sao ấy .

[cansaoviet]

Bài 1: Bao vây

V­ương quốc Flatland có hình chữ nhật kích th­ước M x N ô vuông. V­uơng quốc được chia thành K tỉnh, mỗi tỉnh gồm 1 số ô vuông liên thông với nhau theo tiêu chuẩn kề cạnh. Không có điểm nào của Flatland là điểm biên của hơn 3 tỉnh, tức là không có đỉnh ô vuông nào là điểm chung của 4 tỉnh khác nhau.
Mỗi tỉnh được kí hiệu bằng 1 kí tự có mã ASCII lớn hơn 32. Thủ đô được kí hiệu là A và gồm đúng 1 ô. Thủ đô không phải là ô biên.
Vua của quốc gia thù địch Wrackland muốn thôn tính Flatland. Để làm được chuyện đó, ông ta phải chiếm được thủ đô của Flatland. Tuy vậy ông ta biết rằng quân đội của mình không đủ mạnh để chiếm hết các tỉnh của Flatland, để từ đó chiếm thủ đô. Vị vua độc ác này quyết định chiếm các tỉnh bao quanh thủ đô, vây hãm lâu dài thủ đô Flatland cho đến khi nước này phải đầu hàng.
Để làm được chuyện đó, quân đội Wrackland đánh chiếm một hoặc một số tỉnh biên giới của Flatland , từ đó chiếm tiếp các tỉnh kề với tỉnh đã chiếm được. Trên quan điểm quân sự, phải lên phương án hành động sao cho số tỉnh cần chiếm là ít nhất.
Yêu cầu: Xác định số tỉnh ít nhất mà vua Wrackland cần phải chiếm để vây hãm thủ đô Flatland hoặc cho biết là không thể làm được điều dú (nếu phải chiếm hết các tỉnh của Flatland ngoại trừ thủ đô).
Input: SIEGE.INP gồm nhiều bộ dữ liệu, mỗi bộ gồm 1 số dòng trong đó:
- Dòng đầu chứa 2 số nguyên M, N (3 <=M, N <=200)
- M dòng sau , mỗi dòng chứa N ký tự mã ASCII lớn hơn 32, mô tả các tỉnh của Flatland
- Kết thúc các bộ dữ liệu là dòng chứa 2 số 0 0
Output: SIEGE.OUT mỗi bộ dữ liệu đưa ra 1 số nguyên K tương ứng - số tỉnh ít nhẩ cần đánh chiếm; k=-1 nếu không có phương án
VD: SIEGE.INP
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
33333Z
3 3
BBB
BAB
BBB
0 0
OUT: SIEGE.OUT
4
-1

Ba thành phố

Trong một đất nước có N thành phố được đánh số từ 1 đến N. Có một số thành phố được nối với nhau bởi hệ thống các con đường cao tốc, mỗi con đường nối hai thành phố nào đó. Hệ thống đường cao tốc này có tính chất sau: Đối với hai thành phố bất kỳ A và B, nếu có cách di chuyển từ thành phố A đến thành phố B theo các con đường của hệ thống thì có đúng một cách di chuyển mà trong đó không có con đường nào bị đi qua quá 1 lần.
Tổng thống của dất nước này đặt ra câu hỏi sau đây đối với các nhà Tin học: Ba thành phố nào là cách xa nhau nhất. Chính xác hơn, ta gọi độ giãn cách giữa ba thành phố A, B và C là tổng số con đường cần sử dụng để di chuyển từ A đến B, tiếp đến di chuyển từ B đến C và cuối cùng di chuyển từ C đến A tuân thủ điều kiện: trong mỗi di chuyển vừa nêu, mỗi con đường chỉ được đi qua không quá 1 lần.
Yêu cầu: Tìm ba thành phố mà độ giãn cách giữa chúng là lớn nhất.
Dữ liệu vào : từ file văn bản COUNTRY.INP
- Dòng đầu tiên chứa số nguyên N (3 <=N <=1000)
- Tiếp theo là N dòng mô tả thông tin về các thành phố. Dòng thứ i chứa các số : Ki là số lượng thành phố có con đường nối với thành phố i (1 <=Ki<N), sau đó là Ki số nguyên là các chỉ số của các thành phố này.
Kết quả: ghi ra file văn bản COUNTRY.OUT: một số nguyên là độ giãn cách giữa ba thành phố tìm được
Ví dụ:
INP: 5
1 3
1 3
3 1 2 4
2 3 5
1 4
OUT: 8

Đề bài đây nhé các bạn [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[skyxd88]

Mình xin đóng góp vài ý tưởng về hai bài toán này [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Bài Flatland

Mình nghĩ bài này có thể đồ thị hóa bài toán. Bạn sẽ chuyển ma trận mô tả các tỉnh thành một đồ thị G=(V,E) trong đó tập đỉnh V biểu diễn các tỉnh, mỗi tỉnh sẽ tương ứng với một đỉnh; E là tập cạnh nối với quy ước: giữa hai đỉnh có cạnh nối trực tiếp khi và chỉ khi hai thành phố nằm tiếp giáp nhau trên bản đồ.

Sau khi xây dựng được đồ thị như vậy, ta có nhận xét là để chiếm được thủ đô (đỉnh A) thì phải chiếm tất cả các đỉnh kề với đỉnh A (có tối đa là 4 đỉnh kề với A đúng không [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] ), các đỉnh kề với đỉnh A lại kề với nhau (cái này bạn đọc kĩ đề bài một tẹo sẽ suy ra được). Tức là nếu một đỉnh đã bị chiếm thì ta có thể chiếm luôn hết các đỉnh còn lại trong số các đỉnh kề A.

Thuật toán bây giờ là tìm đường đi ngắn nhất từ một đỉnh A đến biên (Đỉnh biên ứng với tỉnh biên giới ấy). Đến đây thì bạn suy nghĩ một tí rồi xử lí nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Chắc là sẽ ra thôi!


Bài Ba thành phố

Bài này mình mới nghĩ ra thuật toán dùng DFS. Cách này có vẻ hơi khó hiểu và chứng minh khá là rắc rối. Với cả phải dùng hình vẽ để diễn giải. Có gì bạn add nick Yahoo mình rồi trao đổi cho tiện nhé. Nick mình: truelove_bluesky

[myhanh2365]

@trunga0: cám ơn bạn rất nhiều đã chuyển đề bài sang font chữ dễ nhìn, và cũng thanks bạn đã đóng góp ý kiến về bài này.
Bài 1: mọi điều bạn nói đều đúng, nhưng chỉ có 1 điều: tìm đường đi từ 1 ô tới biên không phải dễ dàng, hơn nữa, đây không chỉ là 1 ô mà là nhiều ô trong 1 tỉnh, lại có nhiều tỉnh nên rất rắc rối. Đó là điểm làm mình đau đầu.
Bài 2: nếu đọc kĩ đề bài ta sẽ có thuật toán sau: tìm 2 thành phố A, B có khoảng cách giữa chúng là max, sau đó tìm nốt thành phố C sao cho A->C+B->C max là xong. Nhận xét rằng A và B chắc chắn là nút lá nếu ta coi đồ thị có dạng cây.
Bài 2 hồi trước mình làm rồi, thày giáo đã hướng dẫn nhưng quên mất cách giải, giờ nhớ ra rồi thì lại mệt với phần viết code. Chán!

[npd.fpt01]

Bài hai mình cũng nghĩ giống bạn, mình DFS hai lần để chọn gốc (chọn làm TP A luôn), sau đó DFS một lần nữa là tìm được B và C.

Bài 1 rắc rối là ở chỗ đưa về dạng đồ thị, còn nếu đã xây dựng được đồ thị thì lại thành bài toán loang bt. Để xây dựng đồ thị thì cần xử lí cẩn thận là xong. Đầu tiên bạn xây dựng danh sách các đỉnh, rồi bạn xét các ô kề nhau, giả sử ô thuộc tỉnh 1 kề ô thuộc tỉnh 2 thì bạn đánh dấu là có đường đi giữa đỉnh 1 đến đỉnh 2... Sau đó thì tìm đường đi ngắn nhất như bt thôi, mình nghĩ với bài này dùng Queue vòng sẽ hiệu quả nhất [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[seodinhphong]

Đúng là quan trọng nhất là phải xây dựng được đồ thị nối các đỉnh. Nhưng muốn xây dựng được lại phải duyệt toàn bộ, vậy có cách nào không cần lập đồ thị, chỉ cần duyệt xong cái vương quốc là xong không nhỉ?
Bài 2 giới hạn là 1000 đấy, làm sao để được 100% test đây? 1 vấn đề đau đầu nữa!! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[seobravolaw]

Nếu không lập đồ thị thì bạn có thể làm được nhưng mà xử lí sẽ rắc rối hơn một chút. Vẫn là từ 1 ô có thể đi đến một ô kề cạnh, và bạn tìm đường ngắn nhất từ thủ đô A đi đến biên giới (đi qua tí tỉnh nhất). Nhưng mình nghĩ làm cách này vẫn phải làm bằng thuật toán tìm đường đi ngắn nhất và vẫn là làm trên đồ thị nhưng khác với cách kia (mỗi tỉnh là một đỉnh đồ thị), cách này mỗi ô vuông con sẽ là một đỉnh của đồ thị, nên số đỉnh của đồ thị sẽ lớn hơn nên chạy sẽ chậm hơn.

Còn bài 2 mình không rõ thuật toán của bạn thế nào chứ nếu làm theo kiểu DFS tìm gốc rồi tìm 2 lá xa gốc nhất thì độ phức tạp là O(N) và chạy được hoàn toàn với N = 1000 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[ndt2802]

Bài 2 đơn giản rồi không nói đến nữa, nhưng còn bài 1 nếu lập đồ thị lên thì có lập được không nếu số đỉnh là quá lớn ứng với trường hợp có nhiều tỉnh và giới hạn max.
Bài 1 bạn nói tìm đường đi thì dễ đấy, nhưng phải xử lí làm sao với số lơn đây? Riêng lập cái bảng vương quốc kích thước đã 200*200 rồi, làm gì còn đủ bộ nhớ cho cái gì nữa, chỉ đủ để làm thêm vài mảng nhỏ, muốn loang cũng khó vì đây là tìm đường đi ngắn nhất và phải in ra số tỉnh ngắn nhất. Loang không dùng thêm mảng đánh dấu thì loang ra sao đây?

[teenhotvip]

Bài 1 thì mình nghĩ bạn đồ thị hoá với mỗi tỉnh là một đỉnh ta sẽ có đồ thị ít đỉnh hơn mỗi ô là một đỉnh, do không có điểm nào là là điểm biên của hơn 3 tỉnh mà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Mà mình mới có ý tưởng là ta có thể thêm một đỉnh ảo T mà kề với tất cả các đỉnh biên (các tỉnh biên giới), giờ nhiệm vụ của ta là tìm đường đi ngắn nhất từ A -> T rồi lấy kq trừ đi 1.

200*200 = 40000. Với thuật toán Dijktra Heap độ phức tạp O(N.logN) thì đã đủ chạy với N = 40000 chưa bạn [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]