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

Đề tài: Code bài toán tìm số cách đi trên mạng lưới ô vuông ( Bài Toán khá hay )

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Mặc định Code bài toán tìm số cách đi trên mạng lưới ô vuông ( Bài Toán khá hay )

    Đây là đề bài nè:
    " Cô bé quàng khăn đỏ
    Problem
    Ngày xửa ngày xưa, có một cô bé quàng khăn đỏ sống với mẹ ở một khu rừng nọ, hằng ngày, cô phải hái nấm và mang đến cho bà ngoại của mình ở phía bên kia của khu rừng. Tuy nhiên, trong khu rừng có 3 loại nấm (ký hiệu 1, 2 và 3), tuy nhiên trên con đường có rất nhiều đá (ký hiệu -1) và cô bé phải tránh những đống đá này! Trong rừng có một con sói rất độc ác, nên để không bị con sói phát hiện, mỗi ngày cô phải đi một con đường khác nhau, nhưng vì cô bé rất hiếu thảo, muốn hái thật nhiều loại nấm trong rừng tặng bà, nên trên mỗi con đường cô phải hái được ít nhất 2 loại nấm khác nhau! Các bạn hãy giúp cô bé đếm số cách để đến được nhà bà ngoại mà không bị con sói phát hiện nhé!
    Cách đi: khu rừng là 1 ma trận mxn, mỗi ô có thể kí hiệu là nấm (1, 2, 3), đống đá (-1)), cô bé xuất phát từ 0, 0 ( ô này không có gì,ký hiệu là 0 ) đi đến nhà bà ngoại ở m, n ( ô này cũng không có gì,ký hiệu là 0 ) và cô chỉ được đi sang trái hoặc sang phải.
    Input
    Dòng đầu tiên nhập vào 2 số nguyên dương m và n (m,n<1000) thể hiện cho chiều dài và chiều rộng của khu rừng. m dòng tiếp theo, mỗi dòng có n kí tự (-1, 1, 2 hoặc 3) biểu diễn cho nấm, đá,ô đầu tiên và ô cuối cùng là 0 (giữa 2 kí tự cách nhau 1 khoảng trống).
    Output
    Một dòng duy nhất ghi số cách!
    Mẫu Input
    2 2
    0 1
    0 2
    Mẫu Output
    2"
    Và đây là code của mình ( rất chi là thủ công,mình ko tối ưu hơn đc ,nhưng vẫn đúng ah nha )
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. int m,n;
    4. int Nam[1000][1000],SoCachDi[1000][1000];
    5. void Enter()
    6. {
    7.      int i,j;
    8.      scanf("%d %d",&m,&n);
    9.      for (i=0;i<n;i++)
    10.          for (j=0;j<m;j++)
    11.              scanf("%d",&Nam[i][j]);
    12. }
    13. void Init(int x)
    14. {
    15.      int i,j,k,l;
    16.      SoCachDi[n-1][m-1] = 0;
    17.      if ( x == -1 )
    18.      {
    19.      
    20.           for ( j=n-2;j>=0;j-- )
    21.           {
    22.               if ( Nam[j][m-1] != x )
    23.                   SoCachDi[j][m-1] = 1;
    24.               else
    25.               {
    26.                   for ( k=j;k>=0;k-- )
    27.                       SoCachDi [k][m-1] = 0;
    28.                   break;
    29.               }
    30.           }
    31.           for ( i=m-2;i>=0;i-- )
    32.           {
    33.               if ( Nam[n-1][i] != x )
    34.                  SoCachDi[n-1][i] = 1;
    35.               else
    36.               {
    37.                   for ( l=i;l>=0;l-- )
    38.                       SoCachDi [n-1][i] = 0;
    39.                   break;
    40.               }
    41.           }
    42.      }
    43.      else
    44.      {
    45.          for ( j=n-2;j>=0;j-- )
    46.          {
    47.               if ( Nam[j][m-1] == x )
    48.                  SoCachDi[j][m-1] = 1;
    49.               else
    50.               {
    51.                   for ( k=j;k>=0;k-- )
    52.                       SoCachDi [k][m-1] = 0;
    53.                   break;
    54.               }
    55.          }
    56.          for ( i=m-2;i>=0;i-- )
    57.          {
    58.              if ( Nam[n-1][i] == x )
    59.                 SoCachDi[n-1][i] = 1;
    60.              else
    61.              {
    62.                  for ( l=i-1;l>=0;l-- )
    63.                      SoCachDi [n-1][l] = 0;
    64.                  break;
    65.              }
    66.          }
    67.      }
    68. }
    69. void Optimize()
    70. {
    71.     int i,j;
    72.     for (i=n-2;i>=0;i--)
    73.         for (j=m-2;j>=0;j--)
    74.         {
    75.             if ( Nam[i][j] == -1 )
    76.                SoCachDi[i][j] = 0;
    77.             else SoCachDi[i][j] = SoCachDi[i+1][j] + SoCachDi[i][j+1];
    78.         }
    79. }
    80. void Optimize_extra(int x)
    81. {
    82.     int i,j;
    83.      for (i=n-2;i>=0;i--)
    84.         for (j=m-2;j>=0;j--)
    85.         {
    86.             if ( (Nam[i][j] == x)||((i == 0)&&(j == 0)) )
    87.                SoCachDi[i][j] = SoCachDi[i+1][j] + SoCachDi[i][j+1];
    88.             else SoCachDi[i][j] = 0;
    89.         }
    90. }
    91. int main()
    92. {
    93.     int s,s1,s2,s3;
    94.     Enter();
    95.     Init(-1);
    96.     Optimize();
    97.     s = SoCachDi[0][0];
    98.     Init(1);
    99.     Optimize_extra(1);
    100.     s1 = SoCachDi[0][0];
    101.     Init(2);
    102.     Optimize_extra(2);
    103.     s2 = SoCachDi[0][0];
    104.     Init(3);
    105.     Optimize_extra(3);
    106.     s3 = SoCachDi[0][0];
    107.     printf("%d",s-s1-s2-s3);
    108.     getch();
    109.     return 0;
    110. }
    Các pác thử làm bài này đi xong up code lên cho em tham khảo vs

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Bạn thích làm đề Olympic nhỉ Sao ko post vào chỗ này hả bạn
    http://diendan.congdongcviet.com/sho...=34911&page=62
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Uí trời,đây là bài thi Olympic ah??Năm nào dzậy???Thầy mình "chém" đề đấy chứ

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    À, mấy đề thi Olympic thường có dạng :
    Tiêu đề :
    Bài văn mô tả :
    Yêu cầu cách thức đưa input và output ra cho người ta chấm.:

    Nếu ko là olympic thì cũng là gì gì đấy trong một vài cuộc thi cử.
    Mà mấy cái này thì bạn nên post vào topic kia thì sẽ hay hơn
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    17

    Ok,thks .Mình mới tham gia vào diễn đàn nên chưa biết nhiều,lần sau mình sẽ rút kinh nghiệm.
    Nhưng mình chót post bài này lên đây thì giúp mình lần cuối đi...

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    1

    Mặc định Code bài toán tìm số cách đi trên mạng lưới ô vuông ( Bài Toán khá hay )

    Mọi người có thể giải thích hoạt động của các hàm Enter và Hàm Init cho mình hiểu với được không. Thank mọi ngừoi nhiều

  7. #7
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    140

    Code gì mà dài rứa. Bài này tên là "hái nấm", hình như là cô bé chỉ được đi xuống hoặc là sang phải mới đúng đề. Mình làm rồi. Ngắn gọn, súc tích, đơn giản, hiệu quả,................................... nhưng ko biết có tối ưu không
    Rẹt rẹt..

  8. #8
    Ngày gia nhập
    03 2012
    Nơi ở
    TP. HCM
    Bài viết
    5

    Trích dẫn Nguyên bản được gửi bởi sim Xem bài viết
    Code gì mà dài rứa. Bài này tên là "hái nấm", hình như là cô bé chỉ được đi xuống hoặc là sang phải mới đúng đề. Mình làm rồi. Ngắn gọn, súc tích, đơn giản, hiệu quả,................................... nhưng ko biết có tối ưu không
    ừ, cái đề đi xuống hoặc sang phải mới đúng chứ cứ sang trái rồi lại sang phải thì chỉ có đi trên 1 dòng à.
    Bạn có bài hay thì up lên cho ACE trong 4rum thọ giáo với chứ
    ...Nguyễn Xuân Giềng...

  9. #9
    Ngày gia nhập
    01 2012
    Nơi ở
    localhost
    Bài viết
    140

    Cái này lâu lắc rồi nên ko còn nhớ rõ nữa. Nhưng hình như là tư duy theo bảng quy hoạch động. Mà cũng hơi dài (hơn cả bạn kia nhỉ) :P
    C++ Code:
    1. #include <iostream.h>
    2. #include <fstream.h>
    3. #include <conio.h>
    4.  
    5. struct O
    6. {
    7.        unsigned long int way;
    8.        unsigned long int num;
    9.        O()
    10.        {
    11.            way = num = 0;
    12.        }
    13. };
    14.  
    15. O bang[101][101];
    16. int map[101][101];
    17. int m, n;
    18.  
    19. void nhap()
    20. {
    21.      ifstream f("mushroom.inp");
    22.      f >> m >> n;
    23.      for (int i=1; i<=m; i++)
    24.          for (int j=1; j<=n; j++)
    25.              f >> map[i][j];
    26. }
    27.  
    28. void xuly()
    29. {
    30.      // xu ly hang dau:
    31.      if (map[1][2]!=-1)
    32.         bang[1][2].num = 1;
    33.      for (int j=3; j<=n; j++)
    34.      {
    35.          if (map[1][j]==-1)
    36.             break;
    37.          else
    38.          {
    39.              if (bang[1][j-1].way!=0)
    40.                 bang[1][j].way = bang[1][j-1].way;
    41.              else if (map[1][j-1]!=map[1][j])
    42.                   bang[1][j].way = bang[1][j-1].num;
    43.              else
    44.                  bang[1][j].num = bang[1][j-1].num;
    45.          }
    46.      }
    47.      // xu ly cot dau:
    48.      if (map[2][1]!=-1)
    49.         bang[2][1].num = 1;
    50.      for (int i=3; i<=m; i++)
    51.      {
    52.          if (map[2][1]==-1)
    53.             break;
    54.          else
    55.          {
    56.              if (bang[i-1][1].way!=0)
    57.                 bang[i][1].way = bang[i-1][1].way;
    58.              else if (map[i-1][1]!=map[i][1])
    59.                   bang[i][1].way = bang[i-1][1].num;
    60.              else
    61.                  bang[i][1].num = bang[i-1][1].num;
    62.          }
    63.      }
    64.      // xu ly cac o tu 2,2 -> m,n:
    65.      for (int i=2; i<=m; i++)
    66.      {
    67.          for (int j=2; j<=n; j++)
    68.          {
    69.              if (map[i][j]!=-1)
    70.              {
    71.                 // xu ly o ben trai:
    72.                 if (bang[i][j-1].way!=0)
    73.                    bang[i][j].way = bang[i][j-1].way;
    74.                 else if (map[i][j-1]!=map[i][j])
    75.                      bang[i][j].way = bang[i][j-1].num;
    76.                 else
    77.                     bang[i][j].num = bang[i][j-1].num;
    78.                 // xu ly o phia tren:
    79.                 if (bang[i-1][j].way!=0)
    80.                    bang[i][j].way += bang[i-1][j].way;
    81.                 else if (map[i-1][j]!=map[i][j])
    82.                      bang[i][j].way += bang[i-1][j].num;
    83.                 else
    84.                     bang[i][j].num += bang[i-1][j].num;
    85.              }
    86.          }
    87.      }
    88.      // xu ly o cuoi m,n:
    89.      bang[m][n].way = bang[m-1][n].way + bang[m][n-1].way;
    90. }
    91.  
    92. void xuat()
    93. {
    94.      ofstream f("mushroom.out");
    95.      unsigned long int kq = bang[m][n].way % 10000000;
    96.      f << kq;
    97. }
    98.  
    99. int main()
    100. {
    101.     nhap();
    102.     xuly();
    103.    
    104.     xuat();
    105.     return 0;
    106. }
    Không biết unsigned long int lưu đủ ko ta. Chắc là 1 số bước phải % 1 lần. Mà chắc ko sao đâu
    Với lại theo đề gốc hình như m, n < 101 (1000 chắc cô bé quàng khăn đỏ đi chết luôn )
    Đã được chỉnh sửa lần cuối bởi sim : 01-03-2012 lúc 11:55 PM. Lý do: Confirm lại đề
    Rẹt rẹt..

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

  1. Đoạn code trong sách Ngôn ngữ lập trình C# mình code trên máy thì chạy sai
    Gửi bởi piavg trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 01-07-2012, 11:04 PM
  2. Trả lời: 30
    Bài viết cuối: 15-02-2012, 07:03 PM
  3. Source code build trên Ubuntu có chạy được Trên Linux Kernel không ?
    Gửi bởi trần trân trong diễn đàn Thắc mắc lập trình C/C++ trên Linux
    Trả lời: 0
    Bài viết cuối: 03-11-2010, 09:22 AM
  4. Đoạn code về linked trên C bị lỗi khi build trên Dev C++. Xem giúp mình
    Gửi bởi birthis trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 4
    Bài viết cuối: 06-05-2010, 01:17 PM
  5. Code in ra số nguyên tố và số chính phương của một dãy trên C. Giúp mình kiểm tra code?
    Gửi bởi lavender trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 7
    Bài viết cuối: 07-06-2009, 01:52 PM

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