Untitled
unknown
csharp
10 days ago
3.4 kB
4
Indexable
using System; using System.Collections.Generic; using System.Linq; public class BaiTap69 { static int soThanhPho; static int[,] maTranKe; static List<int> duongDiTimThay = null; static bool TimDuongDi(int hienTai, int dich, List<int> duongDiHienTai, bool[] daTham) { daTham[hienTai] = true; duongDiHienTai.Add(hienTai); if (hienTai == dich) { duongDiTimThay = new List<int>(duongDiHienTai); return true; } for (int ke = 0; ke < soThanhPho; ke++) { if (maTranKe[hienTai, ke] == 1 && !daTham[ke]) { if (TimDuongDi(ke, dich, duongDiHienTai, daTham)) { return true; } } } duongDiHienTai.RemoveAt(duongDiHienTai.Count - 1); return false; } public static void Main(string[] args) { Console.OutputEncoding = System.Text.Encoding.UTF8; Console.InputEncoding = System.Text.Encoding.UTF8; Console.WriteLine("Tìm đường đi giữa các thành phố (đệ quy)"); Console.Write("Nhập số lượng thành phố N (N > 0): "); while (!int.TryParse(Console.ReadLine(), out soThanhPho) || soThanhPho <= 0) { Console.Write("Số lượng không hợp lệ. Nhập lại N: "); } maTranKe = new int[soThanhPho, soThanhPho]; Console.WriteLine("\nNhập ma trận kề (0 hoặc 1):"); for (int i = 0; i < soThanhPho; i++) { for (int j = 0; j < soThanhPho; j++) { if (i == j) { maTranKe[i, j] = 0; continue; } Console.Write($"Nhập A[{i},{j}]: "); int giaTriNhap; while (!int.TryParse(Console.ReadLine(), out giaTriNhap) || (giaTriNhap != 0 && giaTriNhap != 1)) { Console.Write($"Giá trị không hợp lệ. Nhập lại A[{i},{j}]: "); } maTranKe[i, j] = giaTriNhap; } } int thanhPhoBatDau, thanhPhoKetThuc; Console.Write($"\nNhập thành phố bắt đầu (0-{soThanhPho - 1}): "); while (!int.TryParse(Console.ReadLine(), out thanhPhoBatDau) || thanhPhoBatDau < 0 || thanhPhoBatDau >= soThanhPho) { Console.Write($"Thành phố không hợp lệ. Nhập lại: "); } Console.Write($"Nhập thành phố kết thúc (0-{soThanhPho - 1}, khác TP bắt đầu): "); while (!int.TryParse(Console.ReadLine(), out thanhPhoKetThuc) || thanhPhoKetThuc < 0 || thanhPhoKetThuc >= soThanhPho || thanhPhoKetThuc == thanhPhoBatDau) { Console.Write($"Thành phố không hợp lệ. Nhập lại: "); } Console.WriteLine("\n--- KẾT QUẢ ---"); bool[] daTham = new bool[soThanhPho]; List<int> duongDiHienTai = new List<int>(); duongDiTimThay = null; if (TimDuongDi(thanhPhoBatDau, thanhPhoKetThuc, duongDiHienTai, daTham)) { Console.WriteLine($"Đã tìm thấy tuyến đường từ {thanhPhoBatDau} đến {thanhPhoKetThuc}:"); Console.WriteLine(string.Join(" -> ", duongDiTimThay)); } else { Console.WriteLine($"Không tìm thấy tuyến đường nào từ {thanhPhoBatDau} đến {thanhPhoKetThuc}."); } } }
Editor is loading...
Leave a Comment