Đề thi Olympic tin học (về phần mảng tọa độ)

Discussion in 'Olympic Tin học' started by stupid, Aug 27, 2009.

  1. Offline

    stupid

    • New Member

    Message Count:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Bài 2. ĐỊA ĐẠO
    Trong các cuộc kháng chiến chống xâm lược, cha ông ta đã xây dựng các địa đạo rất
    lớn dưới lòng đất với các tuyến đường giao thông ngầm chằng chịt, vừa bảo đảm an
    toàn, vừa giữ bí mật tuyệt đối. Trong địa đạo này giao thông đi lại phải tuân thủ các
    qui định chặt chẽ, tất cả mọi người đều phải di chuyển dọc theo các tuyến đường và
    thực hiện nghiêm ngặt các chỉ dẫn giao thông trên đường.
    Một trong các địa đạo như vậy bao gồm N đường dọc và M đường ngang được mô
    tả như một lưới ô vuông kích thước N x M. Các đường ngang đánh số từ 0 đến M-1
    từ dưới lên trên, các đường dọc đánh số từ 0 đến N-1 từ trái sang phải. Tại một số vị
    trí giao giữa các đường người ta đặt các biển chỉ dẫn dạng hoặc với ý nghĩa
    như sau: khi di chuyển theo các đường tại các nút giao thông, nếu gặp chỉ dẫn thì
    bắt buộc rẽ trái, nếu gặp chỉ dẫn thì bắt buộc rẽ phải, còn nếu không có chỉ dẫn thì
    phải đi thẳng. Sơ đồ sau cho ta một hình ảnh các đường của địa đạo và các chỉ dẫn.



    Bạn có nhiệm vụ dẫn một đoàn khách tham quan đi theo các đường của địa đạo,
    xuất phát từ vị trí (0,0) và tuân thủ chỉ dẫn tại các nút giao thông. Từ vị trí ban đầu
    bạn có thể đi theo một trong hai hướng (ngang hoặc dọc). Đường đi của bạn sẽ dừng
    lại nếu xảy ra một trong hai tình huống sau:
    1. Không thể đi tiếp được nữa.
    2. Nút giao thông sắp đến theo hành trình là nút giao thông đã đi qua.
    Độ dài của đoạn đường đã đi là tổng số các nút giao thông đã đi qua kể cả vị trí xuất
    phát và vị trí kết thúc.
    Yêu cầu: tính độ dài của đoạn đường có thể đi được trong địa đạo.
    Dữ liệu: vào từ file văn bản PIPE.INP có dạng sau:

    • Dòng đầu tiên chứa 3 số tự nhiên là N, M và K với N, M là kích thước của
    lưới mô tả địa đạo. N, M < 100. K là số lượng các chỉ dẫn có tại các nút giao
    thông trong địa đạo. K < 1000. Các số cách nhau bởi dấu cách.
    • K dòng tiếp theo mô tả tọa độ và tính chất của các chỉ dẫn tại các nút giao
    thông tương ứng. Mỗi dòng bao gồm 3 số nguyên dạng X Y Z. Ở đây X, Y là
    toạ độ của vị trí biển chỉ dẫn (0 ≤ X ≤ N-1, 0 ≤ Y ≤ M-1), Z nhận giá trị 0
    hoặc 1 với ý nghĩa: 0 là chỉ dẫn rẽ phải và 1 là chỉ dẫn rẽ trái. Các số cách
    nhau bởi dấu cách.
    Kết quả: ghi ra file văn bản PIPE.OUT bao gồm một dòng chứa đúng 2 số tự nhiên
    theo thứ tự tăng dần là độ dài của hai đường đi trong địa đạo xuất phát từ vị trí ban
    đầu.


    còn dưới cùng là đề đầy đủ mong nhận được sự chỉ giáo của các sư huynh:infatuated:
  2. Offline

    S.Storm

    • Laziz boiz

    Message Count:
    314
    Likes Received:
    44
    Trophy Points:
    28
    Đây thực ra là một bài duyệt mảng theo chiều cho trước.

    B1a: Khởi tạo và đọc dữ liệu

    -Khai báo các biến toàn cục
    Viết hàm viod Input()

    -Mở file
    -Đọc N,M,K
    -Khởi tạo 1 mảng A[N][M] gồm toàn số -1
    -Lặp: Ứng với mỗi dòng trong K dòng tiếp theo, đọc bộ X, Y, Z rồi ghi giá trị Z vào ô A[Y][X]

    Code:
    
    ifstream f;
    f.open ("PIPE.INP");
    f>>M>>N>>K;
    
    int X, Y, Z;
    
    for (int i=0; i<M; i++)
    	for (int j=0; j<N; j++)
    		A[i][j]=-1;  //-1 quy ước là chưa đi qua
    
    for (i=0; i<K; i++)
    {
    	f>>X>>Y>>Z;
    	A[M-1-Y][X]=Z;  //0 hoặc 1 quy ước là có biển báo và chưa đi qua
    //A[M-1-Y]: do đề đánh số dòng ngược từ dưới lên nên cũng duyệt dòng ngược từ dưới lên
    }
    f.close();
    
    B1b: Viết hàm xuất kết quả
    Code:
    void Xuat(int num1, int num2) //ghi 2 số num1, num2 ra file
    {
    	ofstream f;
    	f.open ("PIPE.OUT");
    	f<<num1<<endl;
    	f<<num2;
    	f.close();
    }
    
    B2: Viết hàm int Go(int x, int y)

    -Hàm này sẽ lặp việc duyệt mảng từ A[0][0] theo chiều được quy định bởi x, y (x!=0: đi ngang, y!=0: đi dọc) và trả về giá trị độ dài hành trình
    Code:
    int i=0;
    int j=0;
    
    int len=0;
    
    while (A[M-1-i,j]!=2 && i<M && j<N && i>=0 && j>=0)
    //A[M-1-i]: do đề đánh số dòng ngược từ dưới lên nên cũng duyệt dòng ngược từ dưới lên
    {
    	if (A[M-1-i][j]==1)			//Gặp biển báo, đổi chiều di chuyển, ngược lại thì giữ nguyên x,y
    		TurnLeft(x,y);
    	else if(A[M-1-i][j]==0)
    		TurnRight(x,y);
    	
    	A[M-1-i][j]=2;		//2 quy ước là đánh dấu đã đi
    
    	len++;			//tăng độ dài hành trình
    
    	i+=y;			//di chuyển tới ô tiếp theo, theo chiều quy định của x,y
    	j+=x;			//tại mỗi thời điểm, chỉ có 1 trong 2 biến khác 0
    }
    
    return len;
    
    
    B3: Viết hàm void TurnLeft(int &x, int &y)
    Code:
    if (x==1) //right
    {
    	x=0;
    	y=-1; //up
    }
    
    if (x==-1) //left
    {
    	x=0;
    	y=1; //down
    }
    
    if (y==-1) //up
    {
    	x=-1; //left
    	y=0;
    }
    
    if (y==1) //down
    {
    	x=1; //right
    	y=0;
    }
    
    B4: Viết hàm void TurnRight(int &x, int &y)

    Dựa vào kết quả của TurnLeft, ta đảo dấu 2 biến quy định chiều di chuyển, sẽ được hướng ngược lại

    Code:
    void TurnRight(int &x, int &y)
    {
    	TurnLeft(x,y);
    	x=-x;
    	y=-y;
    }
    
    B5: Viết hàm void main()

    Code:
    Input()
    int len1 = Go(1,0); //đi theo hướng qua phải
    
    Input()            //Init lại mảng A
    int len2 = Go(0,1) //đi theo hướng xuống dưới
    
    Xuat(len1, len2);
    
    
    (Các hàm trong bài viết bằng MS VC++ 6.0, chỉ để tham khảo)
  3. Offline

    conam

    • Active Member

    Message Count:
    152
    Likes Received:
    63
    Trophy Points:
    28
    bạn có thể giải thích giùm mình ý nghĩa của << hay >> mình vẫn chưa hiểu rõ về phép toán dịch chuyển bit.:simper:
  4. Offline

    S.Storm

    • Laziz boiz

    Message Count:
    314
    Likes Received:
    44
    Trophy Points:
    28
    Dấu "<<" hay ">>" là toán tử xuất nhập của C++
    Bạn có thể tham khảo thêm trong Giáo trình LT HĐT bằng C++ của G.S Phạm Văn Ất

    Code:
    [URL]http://sstorm.webng.com/OLP/lthdt.rar[/URL]
    
    Code:
    Password = "diendanspkt.net"
    
  5. Offline

    son.daothanh

    • New Member

    Message Count:
    10
    Likes Received:
    0
    Trophy Points:
    0
    Mình có 1 ý là: "Các bạn ko nên đưa code lên, các bạn nên đưa mã giả lên vì như vậy ai đọc cũng hiểu ý bạn đang muốn làm j. Nếu bạn đưa code của một ngôn ngữ lập trình nào đó thì chỉ có những người rành ngôn ngữ lập trình đó mới hiểu.":football:

Share This Page