Untitled

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}.");
        }
    }
}