• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

[Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Các đề tài, cuộc thi, chủ đề chung của diễn đàn

Điều hành viên: Điều hành

Hình đại diện của người dùng
T7
Thành viên danh dự
Thành viên danh dự
Bài viết: 415
Ngày tham gia: T.Năm 24/05/2007 8:19 pm
Đến từ: Long Xuyên - An Giang
Been thanked: 12 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi T7 » CN 12/09/2010 4:44 pm

Hôm nay rảnh e ngồi optimize code lại, làm giảm thời gian chạy test 6x6 xuống chỉ còn 0,5 giây, vậy mà thời gian chạy test 7x7 vẫn còn khoảng nửa phút :( .


While (i <= you) i++;

NovaFooc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 307
Ngày tham gia: T.Ba 11/08/2009 3:27 pm

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi NovaFooc » CN 12/09/2010 6:22 pm

nửa phút :-O kinh thế nhỉ, mình thua chắc rồi :((

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Hai 13/09/2010 11:06 am

Mình ngưng nhận bài nha. Tuần này kiểm tra nhiều quá nên chưa chấm bài được nhưng mình gợi ý đáp án nè :D

Trước hết là các bạn quên mất mình làm bài trên .NET, có 1 công cụ khá hay, mời các bạn xem qua ;) viewtopic.php?f=57&t=14479

Mà dù không dùng cách trên thì chương trình của mình vẫn chạy nổi test 7x7 ô trống với 3 nhánh cận như sau:

- Nhánh cận 1: Rất dễ: chỉ cần duyệt ô (1, N) mà tổng số ô đã đi chưa đủ N*N - số ô Block thì dĩ nhiên không cần chạy nữa.
- Nhánh cận 2: Bạn có để ý điều này không:

Hình ảnh


Rõ ràng là khi ở biên bên phải (và trái), nếu cứ duyệt đi lên thì chắc chắn sẽ không còn đường đi nữa: loại! Tương tự cho các biên còn lại.

- Nhánh cận 3: Cái này khó thấy hơn, sẽ giúp bạn loại gần hết trường hợp của nhánh cận 2:

Hình ảnh


Xét trường hợp qua phải, nếu ở ô bên phải tiếp theo đã có, mà ô chéo trên và chéo dưới đều chưa đi thì 100% không còn đường đi nữa! Sau khi đặt nhánh cận này, nhánh cận 2 chỉ còn tác dụng ở ô góc, có thể xét dễ hơn!

Trong đáp án mình sẽ dùng:

- Phân ra 4 trường hợp rõ ràng như code của bạn alexanderdna.
- Thêm phần tính thời gian thực hiện để làm rõ hơn của bạn NovaFooc.

Cám ơn các bạn ;) Ngoài ra đặc biệt chú ý test N=10 này nhé (trong hình minh họa mình vẽ 4 ô thôi), chỉ có chương trình của bạn NovaFooc chạy được thôi :D

Hình ảnh

Hình đại diện của người dùng
alexanderdna
Guru
Guru
Bài viết: 214
Ngày tham gia: T.Ba 14/07/2009 11:13 am
Đến từ: Sài Gòn
Has thanked: 3 time
Been thanked: 15 time

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi alexanderdna » T.Hai 13/09/2010 12:05 pm

Bạn Đạt tính kỹ thiệt! Chắc tôi không bao giờ có thể nghĩ tới cái anh nhánh cận 3.

Còn cái N=10 với ô xuất bị bao vây thì khó hiểu quá. Phải chờ coi bài giải ra làm sao mới được.

T7 đã viết:...giảm thời gian chạy test 6x6 xuống chỉ còn 0,5 giây, vậy mà thời gian chạy test 7x7 vẫn còn khoảng nửa phút :( .

Khung 6x6 mà nửa giây thì 7x7 hết hy vọng! Hừ! Minh Đạt chơi ác quá!

Chạy trên C# Console mau hơn WinForm:
FairSearchCs.jpg


Chạy bằng C (do VC++ biên dịch) thì mau hơn nữa:
FairSearchC.jpg

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Hai 13/09/2010 1:08 pm

Hì, cái N=10 đâu có gì đặc biệt, khi load, mình dùng thuật toán loang tìm xem có đường đi (xét tương đối) từ (1; 1) đến (1; N) hay không, cũng không đến nỗi, chỉ duyệt 100 ô với N=10 thôi, không tốn thời gian cho lắm :D

Mình chưa rảnh xem code cụ thể, nhưng hơi bất ngờ vì chương trình của T7 và alexanderdna không giải được, còn của NovaFooc tuy mấy test khác chạy tệ hơn, nhưng test N=10 thì lại ra ngay kết quả :D Để kiểm tra trong lớp xong phải xem ngay :D

NovaFooc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 307
Ngày tham gia: T.Ba 11/08/2009 3:27 pm

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi NovaFooc » T.Hai 13/09/2010 5:17 pm

hehe, bit ngay ct của mình k0 đua nổi mà
kì này tuy có 3 bài dự thi nhưng k0 vì thế mà kém gay cấn, tính thử thách cũng rất thú vị :D

Hình đại diện của người dùng
VuVanHoanh
Thành viên danh dự
Thành viên danh dự
Bài viết: 1259
Ngày tham gia: T.Năm 03/06/2010 9:23 pm
Đến từ: Kim Sơn - Đông Triều - Quảng Ninh
Has thanked: 22 time
Been thanked: 138 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi VuVanHoanh » T.Hai 13/09/2010 8:26 pm

Hố hố, thế là xong thêm kỳ nửa.
Sắp sang kỳ 4, cho đề ngay đi anh Đạt.
Mấy hôm nay bị cấm vận nên không lên clb được. Hjx
:((
Since 2008...
One love! :x

Hình đại diện của người dùng
truongphu
VIP
VIP
Bài viết: 4756
Ngày tham gia: CN 04/11/2007 10:57 am
Đến từ: Cam Đức, Khánh hòa
Has thanked: 14 time
Been thanked: 510 time

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi truongphu » T.Ba 14/09/2010 7:47 am

Giải thưởng:
Hiện tại do chưa có tài trợ nên mình rất tiếc không thể có giải thưởng cho các bạn, nhưng mục đích chính là để nâng cao kỹ năng xử lí tình huống thực tế, nên mong các bạn tham gia cho vui


giải pháp đề nghị:

1- Sau 1 tháng tổng kết qua 4 kỳ (tuần). Bạn nào giành điểm nhiều nhất qua 4 kỳ sẽ được tặng thẻ cào di động trị giá nho nhỏ là 50.000$ gọi là khuyến khích. Trường hợp cùng điểm sẽ tính theo các chỉ số phụ: số kỳ tham gia, điểm đạt được cao nhất trong 1 kỳ...
(Tôi sẽ chuyển khoản đến bạn Đạt tạm thời cho 4 tháng. Xin cho biết số tài khoản VCB qua tin nhắn)

2- Các bạn đạt được kết quả tốt sau nhiều lần tham gia, đương nhiên Admin sẽ chú ý xem xét, sẽ giành những điều kiện tốt nhất để các bạn sinh hoạt trên forum dễ dàng; tham gia nhóm AM...vv
o0o--truongphu--o0o

.........
Ghé thăm:
Chuyện Linh Tinh

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Năm 16/09/2010 6:52 pm

Bài của bạn alexanderdna:

Code:

  1. Imports System.Collections.Generic
  2.  
  3. Public Class frmMain
  4.  
  5.     Const Max As Integer = 7
  6.  
  7.     Dim Blank As Color = Color.White
  8.     Dim Block As Color = Color.Black
  9.  
  10.     'Biến quản lí Label
  11.     Dim Field(,) As Label
  12.     'Cạnh của hội chợ
  13.     Dim Length As Integer = -1
  14.  
  15.     'Mảng chuỗi chứa các dòng
  16.     Dim strRows() As String
  17.  
  18.     'Lưới kiểm tra
  19.     Dim Grid(,) As Boolean
  20.     'Số đường đi
  21.     Dim Solution As Integer
  22.     'Chỉ mục tối đa
  23.     Dim MaxIndex As Integer
  24.     'Giá trị mỗi ô
  25.     Const Visited As Boolean = True 'Cũng là ô cấm
  26.     Const Unvisited As Boolean = False
  27.  
  28.     Structure Cell
  29.         Dim x As Integer
  30.         Dim y As Integer
  31.  
  32.         Public Sub New(ByVal x0 As Integer, ByVal y0 As Integer)
  33.             x = x0
  34.             y = y0
  35.         End Sub
  36.     End Structure
  37.  
  38.     'Ngăn xếp dò đường
  39.     Dim TraceStack As Stack(Of Cell)
  40.  
  41.     Private Sub InitField(ByVal N As Integer)
  42.         Const _Size As Integer = 30
  43.         '===Xóa control cũ===='
  44.         For x As Integer = 0 To Length - 1
  45.             For y As Integer = 0 To Length - 1
  46.                 Me.Controls.Remove(Field(x, y))
  47.             Next
  48.         Next
  49.         '====Tạo control mới===='
  50.         ReDim Field(N - 1, N - 1)
  51.         Dim pnl As Label
  52.         For x As Integer = 0 To N - 1
  53.             For y As Integer = 0 To N - 1
  54.                 pnl = New Label
  55.                 With pnl
  56.                     .Name = "pnl" & x & "_" & y
  57.                     .Size = New Size(_Size, _Size)
  58.                     .Top = y * _Size + _Size
  59.                     .Left = x * _Size + _Size
  60.                     .BackColor = Blank
  61.                     .BorderStyle = BorderStyle.FixedSingle
  62.                 End With
  63.                 Field(x, y) = pnl
  64.                 Me.Controls.Add(pnl)
  65.             Next
  66.         Next
  67.         Length = N
  68.     End Sub
  69.  
  70.     Private Sub butImport_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butImport.Click
  71.         Dim strFileName As String
  72.         Dim tr As System.IO.TextReader
  73.         Dim strData As String
  74.  
  75.         'Mở hộp thoại chọn tập tin
  76.         If dlgOpen.ShowDialog() = Windows.Forms.DialogResult.Cancel Then Exit Sub
  77.  
  78.         strFileName = dlgOpen.FileName
  79.         dlgOpen.Dispose()
  80.  
  81.         'Nhập tập tin
  82.         tr = New System.IO.StreamReader(strFileName)
  83.         strData = tr.ReadToEnd()
  84.         tr.Close()
  85.         tr.Dispose()
  86.  
  87.         'Tách dòng
  88.         strRows = strData.Split(New String() {vbNewLine}, StringSplitOptions.None)
  89.  
  90.         'Tạo lưới
  91.         InitField(strRows(0).Length)
  92.  
  93.         'Khởi tạo ma trận
  94.         ReDim Grid(Length - 1, Length - 1)
  95.         MaxIndex = Length - 1
  96.  
  97.         For x As Integer = 0 To Length - 1
  98.             For y As Integer = 0 To Length - 1
  99.                 'Chỉnh lưới, loại bỏ ô cấm
  100.                 Field(x, y).BackColor = If(strRows(y)(x) = "0", Blank, Block)
  101.                 'Định trị cho ma trận
  102.                 Grid(x, y) = If(strRows(y)(x) = "0", Unvisited, Visited)
  103.             Next
  104.         Next
  105.     End Sub
  106.  
  107.     Sub Visit()
  108.         Dim x As Integer = 0
  109.         Dim y As Integer = 0
  110.  
  111.         Grid(x, y) = Visited
  112.  
  113.         VisitRight(x + 1, y)
  114.  
  115.         VisitDown(x, y + 1)
  116.     End Sub
  117.  
  118.     Sub VisitLeft(ByVal x As Integer, ByVal y As Integer)
  119.         If Grid(x, y) Then Return
  120.  
  121.         Grid(x, y) = Visited
  122.  
  123.         If x = 0 AndAlso y = MaxIndex Then
  124.             If NotMissed() Then
  125.                 Solution += 1
  126.             End If
  127.         Else
  128.             If x = 0 AndAlso y > 1 Then
  129.                 If Not Grid(x, y - 1) Then
  130.                     Grid(x, y) = Unvisited
  131.                     Return
  132.                 End If
  133.             End If
  134.  
  135.             If x > 0 Then VisitLeft(x - 1, y)
  136.  
  137.             If y < MaxIndex Then VisitDown(x, y + 1)
  138.  
  139.             If y > 0 Then VisitUp(x, y - 1)
  140.  
  141.         End If
  142.  
  143.         Grid(x, y) = Unvisited
  144.     End Sub
  145.  
  146.     Sub VisitRight(ByVal x As Integer, ByVal y As Integer)
  147.         If Grid(x, y) Then Return
  148.  
  149.         Grid(x, y) = Visited
  150.  
  151.         If x = 0 AndAlso y = MaxIndex Then
  152.             If NotMissed() Then
  153.                 Solution += 1
  154.             End If
  155.         Else
  156.             If x = MaxIndex AndAlso y > 0 Then
  157.                 If Not Grid(x, y - 1) Then
  158.                     Grid(x, y) = Unvisited
  159.                     Return
  160.                 End If
  161.             End If
  162.  
  163.             If x < MaxIndex Then VisitRight(x + 1, y)
  164.  
  165.             If y < MaxIndex Then VisitDown(x, y + 1)
  166.  
  167.             If y > 0 Then VisitUp(x, y - 1)
  168.  
  169.         End If
  170.  
  171.         Grid(x, y) = Unvisited
  172.     End Sub
  173.  
  174.     Sub VisitUp(ByVal x As Integer, ByVal y As Integer)
  175.         If Grid(x, y) Then Return
  176.  
  177.         Grid(x, y) = Visited
  178.  
  179.         If x = 0 AndAlso y = MaxIndex Then
  180.             If NotMissed() Then
  181.                 Solution += 1
  182.             End If
  183.         Else
  184.             If y = 0 AndAlso x > 1 Then
  185.                 If Not Grid(x - 1, y) Then
  186.                     Grid(x, y) = Unvisited
  187.                     Return
  188.                 End If
  189.             End If
  190.  
  191.             If y > 0 Then VisitUp(x, y - 1)
  192.  
  193.             If x > 0 Then VisitLeft(x - 1, y)
  194.  
  195.             If x < MaxIndex Then VisitRight(x + 1, y)
  196.  
  197.         End If
  198.  
  199.         Grid(x, y) = Unvisited
  200.     End Sub
  201.  
  202.     Sub VisitDown(ByVal x As Integer, ByVal y As Integer)
  203.         If Grid(x, y) Then Return
  204.  
  205.         Grid(x, y) = Visited
  206.  
  207.         If x = 0 AndAlso y = MaxIndex Then
  208.             If NotMissed() Then
  209.                 Solution += 1
  210.             End If
  211.         Else
  212.             If y = MaxIndex AndAlso x < MaxIndex Then
  213.                 If Not Grid(x + 1, y) Then
  214.                     Grid(x, y) = Unvisited
  215.                     Return
  216.                 End If
  217.             End If
  218.  
  219.             If y < MaxIndex Then VisitDown(x, y + 1)
  220.  
  221.             If x > 0 Then VisitLeft(x - 1, y)
  222.  
  223.             If x < MaxIndex Then VisitRight(x + 1, y)
  224.  
  225.         End If
  226.  
  227.         Grid(x, y) = Unvisited
  228.     End Sub
  229.  
  230.     Function VisitAndTrace(ByVal x As Integer, ByVal y As Integer, ByVal direction As Integer) As Boolean
  231.         If Grid(x, y) Then Return False
  232.  
  233.         Grid(x, y) = Visited
  234.  
  235.         If x = 0 AndAlso y = MaxIndex Then
  236.             If NotMissed() Then
  237.                 Solution += 1
  238.                 Return True
  239.             Else
  240.                 Grid(x, y) = Unvisited
  241.                 Return False
  242.             End If
  243.         Else
  244.             'Dead-end checking
  245.             Select Case direction
  246.                 Case 0 'left
  247.                     If x = 0 AndAlso y > 1 Then
  248.                         If Not Grid(x, y - 1) Then
  249.                             Grid(x, y) = Unvisited
  250.                             Return False
  251.                         End If
  252.                     End If
  253.                 Case 1 'right
  254.                     If x = MaxIndex AndAlso y > 0 Then
  255.                         If Not Grid(x, y - 1) Then
  256.                             Grid(x, y) = Unvisited
  257.                             Return False
  258.                         End If
  259.                     End If
  260.                 Case 2 'up
  261.                     If y = 0 AndAlso x > 1 Then
  262.                         If Not Grid(x - 1, y) Then
  263.                             Grid(x, y) = Unvisited
  264.                             Return False
  265.                         End If
  266.                     End If
  267.                 Case 3 'down
  268.                     If y = MaxIndex AndAlso x < MaxIndex Then
  269.                         If Not Grid(x + 1, y) Then
  270.                             Grid(x, y) = Unvisited
  271.                             Return False
  272.                         End If
  273.                     End If
  274.             End Select
  275.  
  276.             If x < MaxIndex AndAlso direction <> 0 Then 'visit right
  277.                 If VisitAndTrace(x + 1, y, 1) Then
  278.                     TraceStack.Push(New Cell(x + 1, y))
  279.                     Return True
  280.                 End If
  281.             End If
  282.  
  283.             If y < MaxIndex AndAlso direction <> 2 Then 'visit down
  284.                 If VisitAndTrace(x, y + 1, 3) Then
  285.                     TraceStack.Push(New Cell(x, y + 1))
  286.                     Return True
  287.                 End If
  288.             End If
  289.  
  290.             If x > 0 AndAlso direction <> 1 Then 'visit left
  291.                 If VisitAndTrace(x - 1, y, 0) Then
  292.                     TraceStack.Push(New Cell(x - 1, y))
  293.                     Return True
  294.                 End If
  295.             End If
  296.  
  297.             If y > 0 AndAlso direction <> 3 Then 'visit up
  298.                 If VisitAndTrace(x, y - 1, 2) Then
  299.                     TraceStack.Push(New Cell(x, y - 1))
  300.                     Return True
  301.                 End If
  302.             End If
  303.         End If
  304.  
  305.         Grid(x, y) = Unvisited
  306.     End Function
  307.  
  308.     Function NotMissed() As Boolean
  309.         For x As Integer = 0 To MaxIndex
  310.             For y As Integer = 0 To MaxIndex
  311.                 If Not Grid(x, y) Then Return False
  312.             Next
  313.         Next
  314.         Return True
  315.     End Function
  316.  
  317.     Private Sub butCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalc.Click
  318.         'Làm lại ma trận
  319.         For x As Integer = 0 To Length - 1
  320.             For y As Integer = 0 To Length - 1
  321.                 Grid(x, y) = If(strRows(y)(x) = "0", Unvisited, Visited)
  322.             Next
  323.         Next
  324.         Solution = 0
  325.  
  326.         Visit()
  327.         lblPathCount.Text = "Số đường đi: " & Solution
  328.     End Sub
  329.  
  330.     Private Sub butPath_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butPath.Click
  331.         'Làm lại ma trận
  332.         For x As Integer = 0 To Length - 1
  333.             For y As Integer = 0 To Length - 1
  334.                 Grid(x, y) = If(strRows(y)(x) = "0", Unvisited, Visited)
  335.             Next
  336.         Next
  337.         'Dò đường
  338.         TraceStack = New Stack(Of Cell)
  339.         If VisitAndTrace(0, 0, 1) Then
  340.             TraceStack.Push(New Cell(0, 0))
  341.             Dim i As Integer = 1
  342.             Dim c As Cell
  343.             While TraceStack.Count <> 0
  344.                 c = TraceStack.Pop()
  345.                 Field(c.x, c.y).Text = i.ToString()
  346.                 i += 1
  347.             End While
  348.         End If
  349.     End Sub
  350. End Class
  351.  


Test:

Test 1: OK
Test 2: OK
Test 3: OK
Test 4: OK
Test 5: OK
Test 6: OK
Test 7: Hết giờ
Test 8: Hết giờ
Test 9: Hết giờ
Test 10: Hết giờ

Điểm test: 3/5

Nhận xét:

Thuật toán của bạn alexanderdna rất hay, code ngắn gọn, rõ ràng, là chương trình duy nhất trong 3 bài dự thi chạy được test 4. Tuy nhiên, bạn lại dùng hàm NotMiss, mỗi lần duyệt đến N^2, mình nghĩ đặt biến đếm sẽ nhanh hơn :) Nhìn chung code của bạn mình không có gì để bắt lỗi được, lại dùng Stack vô cùng hiệu quả, ghi chú rõ ràng. Cố gắng phát huy.

Điểm code: 5/5

Tổng điểm: 8/10

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Năm 16/09/2010 6:52 pm

Bài của bạn NovaFooc:

Code:

Form chính

  1. Public Class frmMain
  2.  
  3. #Region "InitField"
  4.     Const Max As Integer = 7
  5.  
  6.     Dim Blank As Color = Color.White
  7.     Dim Block As Color = Color.Black
  8.  
  9.     'Biến quản lí Label
  10.     Dim Field(,) As Label
  11.     'Cạnh của hội chợ
  12.     Dim Length As Integer = -1
  13.  
  14.     Private Sub InitField(ByVal N As Integer)
  15.         Const _Size As Integer = 30
  16.         '===Xóa control cũ===='
  17.         For x As Integer = 0 To Length - 1
  18.             For y As Integer = 0 To Length - 1
  19.                 Me.Controls.Remove(Field(x, y))
  20.             Next
  21.         Next
  22.         '====Tạo control mới===='
  23.         ReDim Field(N - 1, N - 1)
  24.         Dim pnl As Label
  25.         For x As Integer = 0 To N - 1
  26.             For y As Integer = 0 To N - 1
  27.                 pnl = New Label
  28.                 With pnl
  29.                     .Name = "pnl" & x & "_" & y
  30.                     .Size = New Size(_Size, _Size)
  31.                     .Top = y * _Size + _Size
  32.                     .Left = x * _Size + _Size
  33.                     .BackColor = Blank
  34.                     .BorderStyle = BorderStyle.FixedSingle
  35.                 End With
  36.                 Field(x, y) = pnl
  37.                 Me.Controls.Add(pnl)
  38.             Next
  39.         Next
  40.         Length = N
  41.     End Sub
  42. #End Region
  43.  
  44.     Dim fw As New FindWay
  45.     Dim oke, cached As Boolean
  46.     Dim paths As New List(Of Point()), k As Integer
  47.  
  48.     Private Sub butImport_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butImport.Click
  49.         Dim s As String
  50.         If OFD.ShowDialog = Windows.Forms.DialogResult.OK Then
  51.             Try
  52.                 Dim sr As New IO.StreamReader(OFD.FileName)
  53.                 s = sr.ReadToEnd
  54.                 sr.Close()
  55.             Catch ex As Exception
  56.                 MsgBox(ex.Message)
  57.                 Exit Sub
  58.             End Try
  59.  
  60.             cached = False
  61.             oke = fw.FromString(s)
  62.             If oke Then
  63.                 Dim a(,) As Boolean = fw.ToArray
  64.                 Dim n As Integer = Math.Sqrt(a.Length)
  65.                 InitField(n)
  66.                 For y As Integer = 0 To n - 1
  67.                     For x As Integer = 0 To n - 1
  68.                         If a(x, y) Then Field(x, y).BackColor = Block
  69.                     Next
  70.                 Next
  71.             Else
  72.                 MsgBox("Không thể tìm đường với input đã cho.")
  73.             End If
  74.         End If
  75.     End Sub
  76.  
  77.     Private Sub butCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalc.Click
  78.         If Not cached Then
  79.             If oke Then
  80.                 Dim d1 As Date = Now
  81.                 paths = fw.ListWay
  82.                 Dim d2 As Date = Now
  83.                 cached = True : k = 0
  84.                 lblPathCount.Text = paths.Count
  85.                 MsgBox("Tìm được " & paths.Count & " đường đi trong " & (d2 - d1).TotalSeconds & "s")
  86.             End If
  87.         End If
  88.     End Sub
  89.  
  90.     Private Sub butPath_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butPath.Click
  91.         If oke Then
  92.             If Not cached Then butCalc_Click(Nothing, Nothing)
  93.             If paths.Count > 0 Then
  94.                 For j As Integer = 0 To paths(k).Length - 1
  95.                     Field(paths(k)(j).X, paths(k)(j).Y).Text = j + 1
  96.                 Next
  97.                 k += 1
  98.                 If k = paths.Count Then k = 0
  99.             End If
  100.         End If
  101.     End Sub
  102. End Class
  103.  


Class FindWay:

  1. Public Class FindWay
  2.     Dim a(,), b(,) As Boolean
  3.     Dim size, cond, fill As Integer
  4.     Dim exitPt, vector(3) As Point
  5.     Dim mask As New Stack(Of Point)
  6.     Dim ways As New List(Of Point())
  7.  
  8. #Region "FindWay Algorithm"
  9.     Private Function IsInside(ByVal pt As Point) As Boolean
  10.         Return Not (pt.X < 0 Or pt.Y < 0 Or pt.X > size Or pt.Y > size)
  11.     End Function
  12.  
  13.     Private Function IsNewWay(ByVal pt As Point) As Boolean
  14.         If Not IsInside(pt) Then
  15.             Return False
  16.         Else
  17.             Return Not (a(pt.X, pt.Y) Or mask.Contains(pt))
  18.         End If
  19.     End Function
  20.  
  21.     Private Function Isfilled(ByVal pt As Point) As Boolean
  22.         If Not IsInside(pt) Then
  23.             Return False
  24.         Else
  25.             Return Not b(pt.X, pt.Y)
  26.         End If
  27.     End Function
  28.  
  29.     Private Function FindNextWay(ByVal start As Point) As Point()
  30.         Dim pts As New List(Of Point)
  31.         For j As Integer = 0 To 3
  32.             If IsNewWay(start + vector(j)) Then pts.Add(start + vector(j))
  33.         Next
  34.         Return pts.ToArray
  35.     End Function
  36.  
  37.     Private Function FindNextFill(ByVal start As Point) As Point()
  38.         Dim pts As New List(Of Point)
  39.         For j As Integer = 0 To 3
  40.             If Isfilled(start + vector(j)) Then pts.Add(start + vector(j))
  41.         Next
  42.         Return pts.ToArray
  43.     End Function
  44.  
  45.     Private Sub GoNext(ByVal pts As Point())
  46.         For i As Integer = 0 To pts.Length - 1
  47.             mask.Push(pts(i))
  48.             If mask.Peek = exitPt And mask.Count = cond Then ways.Add(mask.ToArray)
  49.  
  50.             FillExit()
  51.             If fill = 0 Then
  52.                 Dim w As Point() = FindNextWay(pts(i))
  53.                 If w.Length > 0 Then GoNext(w)
  54.             End If
  55.  
  56.             mask.Pop()
  57.             Application.DoEvents()
  58.         Next
  59.     End Sub
  60.  
  61.     Private Sub FillNext(ByVal pts As Point())
  62.         For i As Integer = 0 To pts.Length - 1
  63.             Dim w As Point() = FindNextFill(pts(i))
  64.             If w.Length > 0 Then
  65.                 For j As Integer = 0 To w.Length - 1
  66.                     b(w(j).X, w(j).Y) = True
  67.                 Next
  68.                 fill -= w.Length
  69.                 FillNext(w)
  70.             End If
  71.         Next
  72.     End Sub
  73.  
  74.     Private Sub FillExit()
  75.         b = a.Clone
  76.  
  77.         Dim done As Point() = mask.ToArray
  78.         For j As Integer = 0 To done.Length - 1
  79.             b(done(j).X, done(j).Y) = True
  80.         Next
  81.         fill = cond - done.Length
  82.  
  83.         FillNext(FindNextFill(exitPt + vector(1)))
  84.         If Not b(exitPt.X, exitPt.Y) Then
  85.             b(exitPt.X, exitPt.Y) = True
  86.             fill -= 1
  87.         End If
  88.     End Sub
  89. #End Region
  90.  
  91.     Public Sub New()
  92.         vector(0) = New Point(1, 0)
  93.         vector(1) = New Point(-1, 0)
  94.         vector(2) = New Point(0, 1)
  95.         vector(3) = New Point(0, -1)
  96.     End Sub
  97.  
  98.     Public Function FromString(ByVal s As String) As Boolean
  99.         Dim lines() As String = s.Replace(vbNewLine, "|").Split("|")
  100.         size = lines.Length - 1
  101.         If size < 1 Then Return False
  102.  
  103.         ReDim a(size, size)
  104.         ReDim b(size, size)
  105.         Dim excl As Integer
  106.         exitPt = New Point(0, size)
  107.         For i As Integer = 0 To size
  108.             For j As Integer = 0 To size
  109.                 a(j, i) = CBool(Val(lines(i)(j)))
  110.                 If a(j, i) = True Then excl += 1
  111.             Next
  112.         Next
  113.         cond = a.Length - excl
  114.  
  115.         Return Not (a(0, 0) Or a(0, size))
  116.     End Function
  117.  
  118.     Public Function ToArray()
  119.         Return a
  120.     End Function
  121.  
  122.     Public Function ListWay() As List(Of Point())
  123.         ways.Clear()
  124.         mask.Clear()
  125.         Dim w As Point() = FindNextWay(New Point(-1, 0))
  126.         GoNext(w)
  127.         For j As Integer = 0 To ways.Count - 1
  128.             Array.Reverse(ways(j))
  129.         Next
  130.  
  131.         Return ways
  132.     End Function
  133. End Class
  134.  


Test:

Test 1: OK
Test 2: OK
Test 3: OK
Test 4: Hết giờ
Test 5: OK
Test 6: OK
Test 7: OK
Test 8: OK
Test 9: Hết giờ
Test 10: Hết giờ

Điểm test: 3.5/5

Nhận xét:

Nhìn chung, code của bạn khá tốt, phân chia class tìm đường rõ ràng nhưng cần cố gắng hơn lần sau!

Điểm code: 4/5

Tổng điểm: 7.5/10

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Năm 16/09/2010 6:52 pm

Bài của bạn T7:

Code:

  1. Public Class frmMain
  2.  
  3.     Const MaxN As Integer = 9
  4.     Dim dx() As Short = {0, 1, 0, -1}
  5.     Dim dy() As Short = {-1, 0, 1, 0}
  6.  
  7.     Dim Field(,) As Label
  8.     Dim Free(MaxN + 2, MaxN + 2), Find As Boolean
  9.     Dim Length, LockedField, CountPath, P(MaxN, MaxN), Pt(MaxN, MaxN) As Integer
  10.  
  11.     Private Sub InitField(ByVal N As Integer)
  12.         Const _Size As Integer = 30
  13.         For x As Integer = 0 To Length - 1
  14.             For y As Integer = 0 To Length - 1
  15.                 Me.Controls.Remove(Field(x, y))
  16.             Next
  17.         Next
  18.         ReDim Field(N - 1, N - 1)
  19.         Dim pnl As Label
  20.         For x As Integer = 0 To N - 1
  21.             For y As Integer = 0 To N - 1
  22.                 pnl = New Label
  23.                 With pnl
  24.                     .Name = "pnl" & x & "_" & y
  25.                     .Size = New Size(_Size, _Size)
  26.                     .Top = y * _Size + _Size
  27.                     .Left = x * _Size + _Size
  28.                     .BackColor = Color.White
  29.                     .BorderStyle = BorderStyle.FixedSingle
  30.                 End With
  31.                 Field(x, y) = pnl
  32.                 Me.Controls.Add(pnl)
  33.             Next
  34.         Next
  35.         Length = N
  36.         LockedField = 0
  37.         CountPath = 0
  38.         Find = False
  39.         lblPathCount.Text = "Số đường đi:"
  40.     End Sub
  41.  
  42.     Private Sub KeepResult()
  43.         Dim x, y As Integer
  44.         For x = 0 To Length - 1
  45.             For y = 0 To Length - 1
  46.                 Pt(x, y) = P(x, y)
  47.             Next
  48.         Next
  49.     End Sub
  50.  
  51.     Private Sub butImport_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butImport.Click
  52.         If Me.OpenDialog.ShowDialog = Windows.Forms.DialogResult.OK Then
  53.             Dim x, y As Byte, s As String
  54.  
  55.             Dim f As New IO.StreamReader(Me.OpenDialog.FileName)
  56.             s = f.ReadToEnd : s = s.Replace(vbCrLf, "")
  57.             f.Close()
  58.  
  59.             InitField(Math.Sqrt(Len(s)))
  60.  
  61.             For x = 0 To Length + 1
  62.                 Free(x, 0) = False
  63.                 Free(x, Length + 1) = False
  64.                 Free(0, x) = False
  65.                 Free(Length + 1, x) = False
  66.             Next
  67.             For x = 0 To Length - 1
  68.                 For y = 0 To Length - 1
  69.                     Free(x + 1, y + 1) = True
  70.                     If s.Substring(y * Length + x, 1) = "1" Then
  71.                         LockedField += 1
  72.                         Field(x, y).BackColor = Color.Black
  73.                         Free(x + 1, y + 1) = False
  74.                     End If
  75.                 Next
  76.             Next
  77.             Free(1, 1) = False
  78.             P(0, 0) = 1
  79.         End If
  80.     End Sub
  81.  
  82.     Private Sub DFS(ByRef x As Integer, ByRef y As Integer)
  83.         Dim k, xt, yt As Integer
  84.         For k = 0 To 3
  85.             xt = x + dx(k) : yt = y + dy(k)
  86.             If Free(xt + 1, yt + 1) Then
  87.                 P(xt, yt) = P(x, y) + 1
  88.                 If P(xt, yt) < Length * Length - LockedField Then
  89.                     If Not (xt = 0 AndAlso yt = Length - 1) AndAlso (Length * Length - LockedField - P(xt, yt) >= Length - yt - 1 + xt) Then
  90.                         Free(xt + 1, yt + 1) = False
  91.                         DFS(xt, yt)
  92.                         Free(xt + 1, yt + 1) = True
  93.                     End If
  94.                 ElseIf xt = 0 AndAlso yt = Length - 1 Then
  95.                     CountPath += 1
  96.                     If CountPath = 1 Then KeepResult()
  97.                 End If
  98.             End If
  99.  
  100.         Next
  101.     End Sub
  102.  
  103.     Private Sub butCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalc.Click
  104.         If Find Then Exit Sub
  105.         DFS(0, 0)
  106.         Find = True
  107.         lblPathCount.Text = "Số đường đi: " & CountPath
  108.     End Sub
  109.  
  110.     Private Sub butPath_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butPath.Click
  111.         butCalc_Click(sender, e)
  112.         If CountPath = 0 Then
  113.             MsgBox("Không tìm thấy đường đi nào!", MsgBoxStyle.Information, "Thông báo")
  114.             Exit Sub
  115.         End If
  116.         Dim x, y As Integer
  117.         For x = 0 To Length - 1
  118.             For y = 0 To Length - 1
  119.                 Field(x, y).Text = Pt(x, y)
  120.             Next
  121.         Next
  122.     End Sub
  123. End Class
  124.  


Test:

Test 1: OK
Test 2: OK
Test 3: OK
Test 4: Hết giờ
Test 5: OK
Test 6: OK
Test 7: Hết giờ
Test 8: Hết giờ
Test 9: Hết giờ
Test 10: Hết giờ

Điểm test: 2.5/5.

Nhận xét:

Lần này, bạn vẫn tiếp tục phát huy sở trường của mình là code rất ngắn gọn, súc tích và hiệu quả. Tuy nhiên, rất tiếc code của bạn chỉ đơn thuần dùng DFS, không thể chạy được các test 4 và 7, 8, 9, 10. Cần cố gắng hơn lần sau.

Điểm code: 3/5.

Tổng điểm: 5.5/10

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Năm 16/09/2010 6:54 pm

Đã cập nhật kết quả và đáp án. Mời các bạn bàn luận thêm trước khi có CUỘC THI MỚI

Cám ơn bác Phú đã tài trợ, cháu đã nhận được :)

NovaFooc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 307
Ngày tham gia: T.Ba 11/08/2009 3:27 pm

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi NovaFooc » T.Năm 16/09/2010 7:37 pm

ủa, hôm thứ 7 mình có update code lại
nhớ kì trc cho sửa lại code trc khi hết hạn mà

Hình đại diện của người dùng
alexanderdna
Guru
Guru
Bài viết: 214
Ngày tham gia: T.Ba 14/07/2009 11:13 am
Đến từ: Sài Gòn
Has thanked: 3 time
Been thanked: 15 time

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi alexanderdna » T.Năm 16/09/2010 8:10 pm

Kỳ này cũng cho cập nhật bài dự thi.
Đạt coi lại xem có bỏ sót bài cập nhật của NovaFooc không?

======

Tản mạn:

Hàm NotMissed chắc nên đổi tên thành NotWise (không khôn ngoan)! Và tôi đã té ngửa khi phát hiện ra cái sự khờ dại đó lúc 18g00 ngày Thứ Hai 13/9/2010 (cái sai nhớ lâu).

Đúng ra phải xài biến đếm như bạn Đạt đã gợi ý. Sau khi phát hiện chỗ khờ dại trên, tôi chuyển qua xài hai biến VisitCount (đếm các ô đã đi qua) và TotalCells (tổng số ô trong lưới). Thấy chương trình chạy mau hơn.

Bây giờ tôi đang mắc học. Lát học xong, coi kỹ lời giải, sẽ bàn thêm! :D

NovaFooc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 307
Ngày tham gia: T.Ba 11/08/2009 3:27 pm

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi NovaFooc » T.Năm 16/09/2010 8:19 pm

thật ra test 4,9,10 mình vẫn k0 vượt qua đc
có điều test 6,7 mình test thì k0 bị dính lỗi như vậy :(
code của Đạt xuất đáp số nhanh vãi :P

Hình đại diện của người dùng
alexanderdna
Guru
Guru
Bài viết: 214
Ngày tham gia: T.Ba 14/07/2009 11:13 am
Đến từ: Sài Gòn
Has thanked: 3 time
Been thanked: 15 time

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi alexanderdna » T.Năm 16/09/2010 9:15 pm

Hoành lại "tung hoành tham luận" rồi! Có cái nên nói; có cái không. Nha!
=====

Giải thuật của Đạt có cái bọc viền hay quá. Tôi nhớ trước đó có thử bọc viền, mà không biết sai chỗ nào khiến cho chương trình chạy hết nổi. Bực quá bỏ luôn! Có viền thì khỏi kiểm tra phạm vi chỉ mục ma trận, đỡ khổ phần nào.

Hình đại diện của người dùng
T7
Thành viên danh dự
Thành viên danh dự
Bài viết: 415
Ngày tham gia: T.Năm 24/05/2007 8:19 pm
Đến từ: Long Xuyên - An Giang
Been thanked: 12 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi T7 » T.Năm 16/09/2010 9:28 pm

Hix... :">
While (i <= you) i++;

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Năm 16/09/2010 9:34 pm

NovaFooc:

À mình có thử tải lại, rồi cũng thêm dòng Mask.Clear vào dòng 103 rồi luôn, nhưng chương trình của bạn chỉ mở được test 6, đến test 7 lại lỗi? Bạn thử tải project mình gửi dưới đây (gồm project gốc của bạn, mình có thêm dòng Mask.Clear, phiền bạn downgrade nhé, mình vừa upgrade để xem code) xem trùng không nhé, mình cộng trước cho bạn 1 điểm của test 6! Xin lỗi vì có nhầm lẫn trong lần chấm bài này, mình xin rút kinh nghiệm. Nếu test 7 mở được thì mình (đoán là test 7 chương trình của bạn sẽ chạy tốt) sẽ cộng 1 điểm còn lại.

alexanderdna:

Cám ơn bạn đã nhắc, mình định ghi thêm việc viền biên trong code mà lại quên mất, thật sơ suất quá.

Với thủ thuật này, chúng ta có 2 cái lợi:
- Không cần xét xem việc đi trái/phải/lên/xuống có bị "vượt biên" hay không.
- Dùng nhánh cận 3 dễ dàng mà không cần xét biên.

Còn bạn alexanderdna có gặp vấn đề với biên mình đoán là có lẽ do đánh dấu biên sai? Mình lúc đầu làm không kĩ cũng bị vấn đề này!

Mình (tự) cảm thấy đề này khá hay, các bạn thử bàn luận thêm xem sao. Mà nếu bạn alexanderdna đã cải tiến code, chắc test 10 chạy tốt đúng không :D Test 10 mình thấy là dạng cao hơn của test 4, nhưng thực tế thì vẫn chạy được trong 10s (chương trình mình chạy trong khoảng 5s).

T7:

Không sao đâu, mỗi người có mặt mạnh/yếu khác nhau mà, thích nhất đọc code của bạn, ngắn gọn (dù nhiều khi mò mẫm mãi mới hiểu) và bất ngờ ;) Cứ tiếp tục phát huy nhé.

À, nhờ các bạn lần sau làm bài nếu được cho thêm vài ghi chú nha, mình chấm dễ kiểm tra xem code đó làm gì, như chấm bài của bạn alexanderdna thì rất nhanh và dễ dàng vì bạn ấy chú thích khá kĩ từng chi tiết.

NovaFooc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 307
Ngày tham gia: T.Ba 11/08/2009 3:27 pm

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi NovaFooc » T.Năm 16/09/2010 10:33 pm

chả bit nua, minh lam tren 2005

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: [Cuộc thi] Kỹ năng lập trình - Kì 3 [Khó]

Gửi bàigửi bởi vo_minhdat2007 » T.Sáu 17/09/2010 4:02 am

Project bạn gửi ở trên mở test 7 bị lỗi:
Hình ảnh

Đây là test 7, bạn xem nhé:

  1. 000000010
  2. 000000010
  3. 000000010
  4. 000000010
  5. 000000010
  6. 000000010
  7. 000000010
  8. 111111110
  9. 000000000


Quay về “Đề tài chung”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách