Settlers of Catan, một trò chơi của người Đức ở năm 1995, người chơi tham gia vào cuộc cai trị một hòn đảo bằng việc xây dựng các con đường, các khu định cư, và các thành phố qua các vùng hoang dã chưa được thám hiểm.
Bạn được một công ty phần mềm thuê để phát triển một phiên bản máy tính cho trò chơi này, và bạn được chọn để xây dựng một trong các luật đặc biệt của trò chơi.
Khi trò chơi kết thúc, người chơi mà xây dựng được con đường dài nhất sẽ được thêm 2 điểm thắng cuộc.
Vấn đề gặp phải ở đây là người chơi thường xây dựng các mạng lưới con đường rất phức tạp và không chỉ theo một đường tuyến tính. Vì lý do đó, việc xác định con đường dài nhất không phải đơn giản (mặc dù những người chơi thường có thể thấy ngay lập tức).
Đối chiếu tới trò chơi gốc, chúng ta sẽ giải quyết một vấn đề đơn giản ở đây: Bạn được cho trước một tập các nodes (thành phố) và một tập các cạnh (các đoạn đường) có chiều dài là 1 kết nối các nodes.
Con đường dài nhất được định nghĩa như là đường đi dài nhất trong mạng lưới đường mà không có cạnh nào được dử dụng hai lần. Dù vậy, các nodes có thể được thăm hơn một lần.
Ví dụ: Mạng lưới sau đây chứa một con đường dài nhất là 12.
Input
Input sẽ chứa một hoặc nhiều test cases.
Dòng đầu là số lượng test case T.
Dòng đầu tiên của mỗi test cases chứa 2 số nguyên: số nodes N (2<=N<=25) và số cạnh M (1<=M<=25). M dòng tiếp theo miêu tả M cạnh. Mỗi cạnh được cho bởi các số node kết nối với nhau. Các node được đánh số từ 0 -> N-1. Các cạnh không có hướng. Các node có bậc là 3 hoặc nhỏ hơn. Mạng lưới không cần thiết phải được kết nối thông suốt với nhau.
Output
Với mỗi test case, in ra chiều dài của con đường dài nhất trên một dòng.
Sample
Input
3
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
Output
12
2
12
sample input:
20
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
3 3
0 1
0 2
1 2
2 1
0 1
10 3
0 4
2 4
4 9
10 6
1 4
1 6
1 7
2 3
2 5
6 7
7 6
0 4
0 5
1 2
1 5
2 4
3 4
8 9
0 2
0 6
1 2
1 4
2 6
3 4
4 5
5 6
5 7
8 12
0 4
0 6
0 7
1 2
1 3
1 5
2 3
2 4
3 4
5 6
5 7
6 7
18 18
0 3
0 11
0 12
1 17
2 3
2 16
4 15
4 16
5 7
5 8
6 9
7 8
7 15
9 14
10 11
10 17
11 17
14 15
15 13
0 11
1 3
1 5
2 10
3 8
4 9
4 12
4 13
5 9
5 12
6 8
7 12
8 9
11 1
5 6
15 19
0 1
0 4
0 9
1 10
2 3
2 5
2 13
3 4
3 5
4 6
5 10
6 8
7 12
7 14
8 12
9 11
10 14
11 12
11 13
13 18
0 2
0 6
0 8
1 2
1 9
1 10
2 3
3 4
3 8
4 6
4 12
5 7
5 10
5 12
6 12
7 9
7 10
9 11
25 18
0 9
1 22
2 3
2 6
2 11
3 8
4 16
5 20
7 17
11 16
12 14
12 19
13 21
16 21
17 20
17 24
18 20
19 24
21 20
0 4
0 12
1 8
1 19
2 12
2 15
3 7
3 17
7 10
7 18
8 11
8 18
9 11
9 14
10 11
10 17
12 20
13 15
14 15
17 18
24 2
0 15
4 11
22 24
0 8
0 15
0 21
1 10
1 12
1 18
2 6
2 9
2 19
3 17
3 19
4 6
5 13
5 19
5 20
7 15
7 18
7 21
9 20
11 13
11 14
11 21
12 15
18 20
22 9
0 20
2 11
2 20
4 9
7 15
9 19
14 17
16 18
19 20
Code Solution:
package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* ý tưởng thuật toán bài này là backTracking
* nhằm sinh ra tất cả các cấu hình rồi tim ra đoạn đường có chiều dài lớn nhất
* lưu ý ở đây là đường đi có thể đi qua đỉnh nhiều hơn 2 lần và chỉ đi qua 1 cạnh duy nhất 1 lần
* (theo đề cho là như vậy)
*/
public class TheSettlersOCatan {
Scanner sc = new Scanner(System.in);
int t, n, m, x, y, count, ans;
int map[][];
boolean visit[][];
void init() {
count = 0;
ans = 0;
map = new int[n + 1][n + 1];
visit = new boolean[n + 1][n + 1];
}
void backTrack(int index) {
if(count > ans) {
ans = count;
}
for(int i=0; i<n; i++) {
if(!visit[index][i] && !visit[i][index] && map[index][i]==1) {
visit[index][i] = true;
visit[i][index] = true;
count++;
//System.out.println(index+” – “+i+”: “+count);
backTrack(i);
// để biết tại sao lại có đoạn code bên dưới này thì 1 làm xem form chuẩn của backTracking
// còn thực tế hơn thì vẽ ra giấy ra or System.out.println(index+” – “+i+”: “+count); để coi đường đi là thấy
visit[index][i] = false;
visit[i][index] = false;
count–;
}
}
}
void solution() {
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
m = sc.nextInt();
init();
for (int i = 0; i < m; i++) {
x = sc.nextInt();
y = sc.nextInt();
map[x][y] = 1;
map[y][x] = 1;
}
// duyệt tất cả các trường hợp xuất phát từ 1 đỉnh bất kỳ để tìm đoạn đường có độ dài lớn nhất
for(int i=0; i<n; i++) {
backTrack(i);
}
System.out.println(ans);
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“TheSettlersOCatan.txt”));
TheSettlersOCatan so = new TheSettlersOCatan();
so.solution();
}
}
alexishuuuocn 