问用图论来编写算法

EN

我不知道这里是不是问这个的好地方。所以我很抱歉，如果我在一个错误的论坛。

我如何以算法的方式解决下面的问题？

房间里有n个箱子。除了一个，他们都有一个橘子在里面。X先生想要在没有打开它的的情况下找到空的盒子(也就是说，如果他打开空的盒子，他会输掉游戏!)每个盒子里可能有一些关于其他盒子的信息，如果X先生读到，这些信息可以找出另一个盒子是否是空的。我们(作为一个知情的第三方人士)写了一张关于盒子和信息的表格，交给X先生。这个表格是一个矩阵，如果M( i，j) = 'Y‘，这意味着在第一框中有一些关于j框的信息，你可以通过打开框i，如果M(i，j) = 'N’来判断它是否是空的，如果M(I，j)=‘N’，这意味着盒子I中没有关于j框的信息。想象X先生最好地使用表打开这些盒子(也就是说，他尽可能少地打开盒子)。现在，计算在不打开空框的情况下找到它的可能性。注意:所有的框都有相同的概率为空或不空。

示例1：

YYYYY
NYNNN
NNYNN
NNNYN
NNNNY

概率: 0.8

示例2：

YYNNY
NYNNY
NNYYY
NNNYY
NNNNY

概率: 0.6

希望有人能帮我。非常感谢。

更新:优化意味着尽可能少地打开他不知道的关于的框(也就是说，如果您知道它，就可以简单地打开它)。