معطى مصفوفة ثنائية مكونه من 0 و 1 . المطلوب ايجاد بئر.
بئر هو الوضع الذي فيه السطر K مكون فقط من اصفار وفي العامود K فقط الرقم 1, نقطة الالتقاء هي 0, مثال:
0 1 1 1 1 0
0 0 1 1 0 0
0 0 1 1 0 1
0 0 0 0 0 0
0 0 1 1 0 1
1 1 1 0 1 0
في هذه المصفوفه الاجابة هي K=3
يجب حل المسألة بنجاعة أقل من (O(n^2
لا يهم باي لغة الحل فانا استطيع الترجمة من كل اللغات الى C#
الفكرة هي التخلي عن جميع الاحتمالات اللتي من المستحيل ان يكون بها بئر ونبقى في النهاية مع احتمال واحد فقط ثم نفحصه
البساوودوكود
Lets look at cell (i,j), for i<>j:
If it's 0, then there's no hole j (all the cells in column j must be 1, other than j,j).
If it's 1, then there's no hole i (all the cells in row i must be 0).
Conclusion: There can be only one hole (if any).
So all we have to do is to eliminate all options except one, and then test it.
Set i=0, j=1
Check cell (i,j)
If (i,j)=0, there's no hole j, set j=j+1.
If (i,j)=1, there's no hole i, set i=j, j=j+1.
Repeat until j=N, then test if hole i exists.
N-1 steps for the eliminations
2N-1 steps for the checking hole i
Total - O(N).
التعليقات