Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    heocoiminmin


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Mọi người xem giúp em phần tìm đường đi với, khi em chạy nó in ra màn hình đc mỗi điểm đầu, điểm cuối, còn các điểm khác toàn địa chỉ thôi. Ai biết chỉ giùm em với, cảm ơn mọi người nhiều ạh!!!
    Đề bài: Tìm đường đi ngắn nhất của quân mã khi cho trước vị trí xp và vị trí đích, quân mã không đc đi qua những ô đã có quân trên bàn cờ
    Ý tưởng:
    - nhập file dữ liệu vào
    - đưa ra ma trận có -1(những ô cấm) và 0
    - gán mỗi ô trên bàn cờ một số thứ tự (VD bàn cờ 8*8 thì có số tt từ 0->63)
    - tạo ma trận kề thể hiện những ô mà mã có thể đi
    - áp dụng giải thuật BFS tìm đường đi ngắn nhất

    File Input.inp
    Code:

    4    // kích thước bàn cờ n * n
    2    // Số ô cấm trên bàn cờ
    0 0  // Vị trí xuất phát
    3 3  // Vị trí kết thúc
    1 1  // còn lại là tọa độ các ô cấm
    3 2
    Code:

    //≡≡--KHAI BAO THU VIEN-≡≡≡≡≡≡≡≡≡≡
    #include<fstream.h>
    #include<conio.h>
    #include<iomanip.h>
    #include<iostream.h>

    #define MAX 10

    //≡---CAC CAU TRUC DU LIEU SE SU DUNG-≡≡≡≡≡≡--

    // cau truc cua 1 o trong Ban Co
    struct ToaDo
    {
      int dong;
      int cot;
    };

    // cau truc cua 1 Ban Co nxn
    struct BanCo
    {
      int n;
      int m[MAX][MAX];
    };

    //≡---KHAI BAO BIEN TOAN CUC-≡≡≡≡≡≡≡--

    // nuoc di cua con ma
    int DX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
    int DY[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

    BanCo bc; // khai bao Ban Co

    ToaDo bd; // diem bat dau di
    ToaDo kt; // diem ket thuc
    int soocam;//soocam
    ToaDo cam[MAX];// toa do cac o cam
    int x[MAX][MAX];//mang luu so thu tu cua cac o
    int L[MAX*MAX][MAX*MAX]={0};// mang luu tru ma tran ke
    int vtc[MAX];

    //≡---CAC HAM SE SU DUNG-≡≡≡≡≡≡≡≡-

    //*********CHU THICH BAN CO**************
    // -1 : o cam
    // 0 : o nay Ma duoc phep di
    //***************************************

    //≡≡-DUA VAO FILE INPUT-≡≡≡≡≡≡≡-

    void NhapInput()
    {
      ifstream ifs( "Input.inp" );
      ifs>>bc.n;

      ifs>>soocam;

      ifs>>bd.dong;
      ifs>>bd.cot;

      ifs>>kt.dong;
      ifs>>kt.cot;

      FOR(int i=0; i<soocam; i++)
      {
        ifs>>cam[i].dong;
        ifs>>cam[i].cot;
      }
      ifs.close();
    }

    //≡≡---XUAT FILE RA MAN HINH-≡≡≡≡≡≡≡≡-

    void Xuat()
    {
        cout<<endl;
        cout<<" Kich co ma tran: "<<bc.n<<" dong x "<<bc.n<<" cot"<<endl<<endl;
        cout<<" So o cam: "<<soocam<<endl<<endl;
        cout<<" Diem khoi hanh: ("<<bd.dong<<", "<<bd.cot<<")"<<endl<<endl;
        cout<<" Diem ket thuc: ("<<kt.dong<<", "<<kt.cot<<")"<<endl<<endl;
        cout<<" Toa do cac o cam: "<<endl<<endl;
        FOR(int i=0; i<soocam; i++)
        {
          cout<<"\t"<<"("<<cam[i].dong<<",";
          cout<<cam[i].cot<<")";
          cout<<endl;
          cout<<endl;
        }
    }
    //≡≡≡--DAT CAC O CAM VAO BAN CO-≡≡≡≡≡≡≡-

    void DuaOCamVaoBanCo()
    {
          FOR(int k=0; k<soocam; k++)
          bc.m[cam[k].dong][cam[k].cot]=-1;

          FOR(int i=0; i<bc.n; i++)
       FOR(int j=0; j<bc.n; j++)
       if( bc.m[i][j]==0) bc.m[i][j]=0;
    }

    //≡≡≡--IN BAN CO RA MAN HINH ≡≡≡≡≡≡≡≡≡

    void XuatBanCo()
    {
        cout<< " Chu thich: " <<endl<<endl;
        cout<< "\t-1: la o cam" <<endl<<endl;
        cout<< "\t 0: la o con Ma duoc phep di" <<endl<<endl;

        FOR(int i=0; i<bc.n; i++)
        {
       FOR(int j=0; j<bc.n;j++)
       cout<< setw(4) << bc.m[i][j];
       cout<< endl;
       cout<< endl;
        }
    }

    //≡≡≡≡-DAT SO THU TU TU 0>63 VAO BAN CO-≡≡≡≡

    void Chuyen_64()
    {
        FOR(int i=0; i<bc.n; i++)
        FOR(int j=0; j<bc.n; j++)
        x[i][j]=bc.n*i+j;
    }

    //≡≡≡≡--IN SO THU TU CUA CAC O TRONG BAN CO RA-≡≡≡≡≡

    void In_64()
    {
        cout<<" Cho moi o trong ban co chua 1 so thu tu: "<<endl<<endl;
        FOR(int i=0; i<bc.n; i++)
        {
       FOR(int j=0; j<bc.n; j++)
       cout<<setw(3)<<x[i][j]<<" ";
       cout<<endl;
       cout<<endl;
        }
    }

    //≡≡≡≡≡-XET VI TRI CAM-≡≡≡≡≡≡≡≡-
    int vtcam(int x)
    {
          FOR(int i=0; i<soocam; i++)
          if(cam[i].dong*bc.n + cam[i].cot == x) return 0;
    }

    //≡≡≡---KIEM TRA 1 O CO THE DI DUOC KHONG-≡≡≡≡--

    int CheckToaDo( ToaDo p )
    {
        // neu khong dam bao nam trong ban co thi khong duoc phep di
        if( p.dong<0 || p.cot<0 || p.dong>=bc.n || p.cot>=bc.n ) return 0;

        // neu la o cam thi khong duoc phep di
        if( bc.m[p.dong][p.cot] == -1 ) return 0;
        return 1;

    }// kiem tra toa do 1 o

    //≡≡≡≡≡≡---TAO RA MA TRAN KE-≡≡≡≡≡≡≡--

    void TaoMaTranKe()
    {
        ToaDo go;
        int i;

        FOR(i=0; i<bc.n*bc.n; i++) // chay het tat ca cac so thu tu cua n*n o
        if(vtcam(i))
        {
       int m=i/bc.n ; // toa do dong cua dinh thu i
       int n=i%bc.n ; // toa do cot cua dinh thu i

       //xet dinh i co the lien thong den dinh nao do khac

       FOR(int k=0; k<=7; k++)// xet 8 vi tri cua con Ma
       {
         go.dong = m +DX[k];// toa do dinh tiep theo
         go.cot = n +DY[k];

         //neu lien thong
         if(CheckToaDo(go))
         {
           L[i][go.dong * bc.n + go.cot]=1; // gan duong di vao ma tran ke
           L[go.dong * bc.n + go.cot][i]=1; // gan duong di vao ma tran ke
         }
       }
        }
    }

    //≡≡≡≡≡≡-XUAT MA TRAN KE-≡≡≡≡≡≡≡--

    void xuat()
    {
        FOR(int i=0; i<bc.n*bc.n; i++)
        {
       FOR(int j=0; j<bc.n*bc.n; j++)
       cout<<L[i][j]<<"  ";
       cout<<endl;
       cout<<endl;
        }
    }

    //≡≡≡≡≡≡≡--MIN PATH-≡≡≡≡≡≡≡≡≡-
    class queue
    {
      int cuoi, dau;
      int q[MAX];
    public:

    queue()
    {
      cuoi = -1;
      dau = 0;
    }
    int empty()
    {
      if (dau > cuoi)
      return 1;
      return 0;
    }
    int full()
    {
      if (cuoi == MAX)
      return 1;
      return 0;
    }
    void insert(int x)
    {
      cuoi++; // tang cuoi len 1
      if (full())
      cout<<"Queue tran!";
      ELSE
      q[cuoi] = x;
    }
    int remove()
    {
      int x;
      if (empty())
      cout<<"Queue Ø!";
      ELSE
      x = q[dau++];
      return x;
    }
    };


    int MinPath(int s, int f, int visit[], int truoc[])
    {

      queue q;

        q.insert(s);  //bo sung s

        WHILE(!q.empty())
        {

          s = q.remove();  // lay s ra
          if (!visit[s]) visit[s]=1;
          if (s == f) return 1;

          FOR(int i = 0; i < bc.n*bc.n; i++)
       if(L[s][i] == 1 && visit[i]==1)
         {
         visit[i]=1;
         truoc[i]=s;
         q.insert(i);
         }
          }//end WHILE
    }

    //≡≡≡≡≡≡≡---DUONG DI-≡≡≡≡≡≡≡≡≡≡--

    void DuongDi()
    {
    int visit[MAX];
    int truoc[MAX];

    int s=x[bd.dong][bd.cot];
    int f=x[kt.dong][kt.cot];
    int path[MAX];

    int kq= MinPath(s,f,visit,truoc);

    if (kq==1)
     {
      int dem=0;
      path[dem++]=f;
      WHILE(f!=s)
      {

        f=truoc[f-1];
        path[dem++]=f;
      }
      cout<<"Co duong di la:  ";
      FOR(int i=dem-1; i>=0; i--)
      cout<<path[i]<<"    ";
      cout<<endl;
     }
    ELSE
      cout<<" Khong co duong di"<<endl;
    }

    //≡≡≡≡≡≡≡-MAIN-≡≡≡≡≡≡≡≡≡≡≡

    void main()
    {
        NhapInput();
        Xuat();
        DuaOCamVaoBanCo();
        XuatBanCo();
        Chuyen_64();
        In_64();
        TaoMaTranKe();
        xuat();
        DuongDi();
      getch();
    }

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs