Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: bài toán lưới mảng hai chiều

  1. #1
    Ngày gia nhập
    02 2008
    Nơi ở
    thành phố hồ chí minh
    Bài viết
    7

    Wink bài toán lưới mảng hai chiều

    Cho lưới ô vuông kích thước M x N. các ô của lưới được sơn bởi một trong hai màu đen hăng trắng
    Cần tìm hình vuông gồm toàn ô đen có kích thước lớn nhất
    Dữ liệu vào:
    File văn bản: LUOI.INP có cấu trúc như sau:
    Dòng đầu ghi hai số M,N
    Trong m dòng tiếp theo mỗi dòng ghi N số , trong đó a[I,j]=1 nếu ô (i.j) có màu đen và a[I,j]=0 nếu ô(I,j) có màu trắng
    Kết quả:
    Ghi ra file văn bản LUOI.OUT có cấu trúc như sau:
    Dòng thứ nhất ghi số k là kích thước của hình vuông tìm được
    Dòng thứ hai ghi 4 số p,q,r,s. trong đó (p,q) là tọa độ của ô ở góc trên trái còn (r,s) là tọa độ của ô ở góc dưới bên phải của hình vuông tim được.
    Ví dụ:
    LUOI.INP
    8 10

    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1

    LUOI.OUT
    4
    5 6 8 9


    có huynh vip nào có ý tưởng giải hay nói cho đệ nghe với
    Đã được chỉnh sửa lần cuối bởi tuan_anhhhh : 27-02-2008 lúc 07:29 PM. Lý do: đánh sai mấy lổi

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Trích dẫn Nguyên bản được gửi bởi tuan_anhhhh Xem bài viết
    Cho lưới ô vuông kích thước M x N. các ô của lưới được sơn bởi một trong hai màu đen hăng trắng
    Cần tìm hình vuông gồm toàn ô đen có kích thước lớn nhất
    Mình có chút suy nghĩ thế này:

    1.Khởi tạo các biến
    Code:
      a. int count=0;//dùng lưu tình trạng diện tích hình vuông là lớn nhất
      b. int p,q,r,s để lưu tọa độ của bạn( thực ra cái này thừa) vì chỉ cần lưu p,  q (+ count) -> r,s.
    1.Bạn cho chạy từ A[0][0] đến A[m][n]
    2.Nếu gặp A[i][j]=1 thì bắt đầu kiểm tra loang bằng cách. Mở rộng diện tích từ count.
    Duyệt hình vuông rộng ra bằng cách duyệt hình vuông cạch =count+1.
    Nếu gặp 0 và cạnh < count+1 thì chuyển sang ô kề.
    Ngược lại thì duyệt theo hình vuông xoắn ốc (hoặc kiểm tra các ô lân cận trong giới hạn hình vuông A[i+Count+1][j+Count+1]).
    Nếu có ô bằng 0 thì chuyển ngược lại update các thông số Count, p, q, r, s.
    3.Lặp lại như vậy cho đến hết
    Đó là chút ý tưởng của mình. Để mình suy nghĩ thêm đã.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  3. #3
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mình có ý nghĩ sau:
    Với ma trận đã có như trên:
    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    m=8, n=10
    Ta làm như sau:

    1. Lần lượt xét từng ô có giá trị là 1 trong ma trận 7*9. (Bởi hàng cuối và cột cuối chỉ bổ sung cho các ô vuông khi ta xét những ô ở hàng 7, và cột 9). Ma trận cần xét là màu đỏ.

    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1

    2. Với 1 ô xét (màu đỏ) ta sẽ:
    - int temp=1;
    - Xét các ô kề (ô có màu xanh dương). Nếu các ô màu xanh dương đều là 1 ta sẽ xét tiếp các ô kề (ô màu xanh lá cây) và lưu lại kích thước lớn nhất tạm thời (tức temp++). Còn nếu ô nào có giá trị 0, ta lập tức đổi giá trị các ô cùng hàng trước nó thành giá trị 0, hay cùng cột trên nó. Đoạn giải thuật này giúp ta sẽ xóa đi những ô có giá trị bằng 1 tiếp theo trong chu trình đi (để khỏi phải xét nữa).
    - k=(k<temp?;temp;k);

    VD:
    - Thứ tự xét:
    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1


    - Khi xét các ô màu xanh dương đều là 1, ta xét tiếp các ô màu xanh lá. Gặp trường hợp có giá trị 0 (có 2 ô là 0). Ta đổi những giá trị trước và trên thành 0 (màu tím)
    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1


    - Như vậy sau khi xét ô màu đỏ ta có k=2, và sau này sẽ không phải xét các ô màu tím nữa vì đã đổi giá trị thành 0.

    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1


    - Bởi ta có xét các ôđó thì kết quả cho kích thước lớn nhất cũng chỉ nhỏ hơn hoặc bằng k vừa tính được. Ví dụ sau ta chọn ô đỏ để xét, ta cũng chỉ xét được với những ô màu xanh dương là tạo thành hình vuông, còn những ô màu xanh lá thì không tạo được (vì có một ô có giá trị 0).

    0 1 0 0 0 0 0 0 0 0
    1 1 1 1 0 0 1 1 1 1
    1 1 1 1 0 0 1 1 1 1
    0 0 1 1 1 0 0 0 0 0
    0 0 1 1 1 1 1 1 1 0
    0 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 0 1 1 1 1 1

    3. Cứ như vậy xét hết ma trận 7*9, cuối cùng ta sẽ có được kích thước lớn nhất.

    Ý mình là vậy, giải thuật này đã giảm phần nào một số ô không phải xét.
    Anh em góp ý thử nha, mình không có thời gian cài đặt chạy thử.
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 28-02-2008 lúc 05:17 PM.
    Không biết ghi gì luôn ...

  4. #4
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Còn nếu ô nào có giá trị 0, ta lập tức đổi giá trị các ô cùng hàng trước nó thành giá trị 0, hay cùng cột trên nó. Đoạn giải thuật này giúp ta sẽ xóa đi những ô có giá trị bằng 1 tiếp theo trong chu trình đi (để khỏi phải xét nữa).
    Ý tưởng của bạn cũng gần giống với tôi. Có đôi chỗ rút gọn hơn.
    Tuy nhiên bạn cũng không cần phải thay đổi mọi cái đã đi rồi thành 0 đâu.
    Như bạn biết khi xét tại tọa độ đỉnh A[i][j] (đỉnh trên bên trái) và bạn đã xác định được kích thước hình vuông là max. Như vậy lần xét tiếp nếu trên một hàng bạn chỉ việc dịch chuyển A[i][j+count] mà thôi.
    Để tối ưu thêm bạn tạo một biến Tmp để lưu cái vị trí mà nó gặp 0 lần sau cũng sẽ nhảy luôn đến A[i][j +Tmp+1];
    Tức là chúng ta tiến hành nhảy cách luôn.
    Nói chung nó vẫn phải là tính toán từng khu vực kết hợp thử sai.
    Suy nghĩ vậy.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  5. #5
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi NT_OnlyLove Xem bài viết
    Tuy nhiên bạn cũng không cần phải thay đổi mọi cái đã đi rồi thành 0 đâu.
    Như bạn biết khi xét tại tọa độ đỉnh A[i][j] (đỉnh trên bên trái) và bạn đã xác định được kích thước hình vuông là max. Như vậy lần xét tiếp nếu trên một hàng bạn chỉ việc dịch chuyển A[i][j+count] mà thôi.
    Để tối ưu thêm bạn tạo một biến Tmp để lưu cái vị trí mà nó gặp 0 lần sau cũng sẽ nhảy luôn đến A[i][j +Tmp+1];
    Tức là chúng ta tiến hành nhảy cách luôn.
    Nói chung nó vẫn phải là tính toán từng khu vực kết hợp thử sai.
    Suy nghĩ vậy.
    Có nhất thiết phải như vậy (có tối ưu) ko? Bởi ta thêm biến, vài dòng lệnh nhảy như bạn thì chương trình dễ rối hơn. Cái đó chỉ dành cho những người đã kinh nghiệm rồi. Ở đây ta nên tường thuật từng bước cho các bạn dễ hiểu hơn mà.
    Không biết ghi gì luôn ...

  6. #6
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Mặc định bài toán lưới mảng hai chiều

    Trích dẫn Nguyên bản được gửi bởi ht961711 Xem bài viết
    Có nhất thiết phải như vậy (có tối ưu) ko? Bởi ta thêm biến, vài dòng lệnh nhảy như bạn thì chương trình dễ rối hơn. Cái đó chỉ dành cho những người đã kinh nghiệm rồi. Ở đây ta nên tường thuật từng bước cho các bạn dễ hiểu hơn mà.
    Nếu bài này ngoài dùng các biến index thì mình cũng không phải thêm nhiều lắm. Với lại thêm một biến Flag như vậy thì khỏi phải triển khai các bước update lại các ô thành 0, và vòng lặp cũng không phải chạy lại khi ta đã chạy qua rồi.
    Nói chung là trao đổi để đưa ra cách tốt nhất mà bạn.
    Mình đồng ý với bạn là cho mọi người hiểu.(Cách hình minh họa của bạn vậy rất là hay, mình không có thời gian nên chỉ nói qua về suy nghĩ riêng).
    Hôm trước xem qua nên cũng không có suy nghĩ sâu được và cũng không code được luôn.
    Thân.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này trước có suy nghĩ lâu lắm, cài đặt thì cũng vất vả kinh khủng, hồi có làm trúng được vài test nhưng vẫn chưa tổng quát lắm. Do làm thấy tốn thời gian quá nên bỏ luôn tới h T_T. Hi vọng lần này giải được hoàn thiện. Ht và Onlylove thử cài đặt xem sao

Các đề tài tương tự

  1. Trả lời: 2
    Bài viết cuối: 21-04-2013, 09:46 AM
  2. Lỗi: bố cục trang web tự tăng theo chiều ngang khi chiều cao thay đổi
    Gửi bởi tuanngocpt trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 2
    Bài viết cuối: 16-03-2013, 11:25 PM
  3. Trả lời: 1
    Bài viết cuối: 28-04-2012, 09:43 PM
  4. Cách truyền mang 1 chiều cho hàm bài con trỏ và mảng một chiều ai có thể giải thích giúp mình
    Gửi bởi biencute trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 21-03-2012, 09:00 AM
  5. Lời giải bài tập: Chuỗi Ký tự, mảng số nguyên 1 chiều, mảng 2 chiều, tạo Menu
    Gửi bởi xuanngoc trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 15-10-2011, 01:17 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn