\(N=1\) ならば Yes、\(N=2\) の時は 0 が \(1\) 個以上ある場合かつその時に限り Yes です。以下、\(N\geq3\) とします。

まず、\(1\) 回目の質問では「\(r=A\) または \(c=B\) を満たす \((r,c)\) であって \(S_{r,c}=\) 0 を満たすものが存在する」ような \((A,B)\) で質問する必要があります(以下、これを良い質問と呼びます)。もしすべて1であるような \(A,B\)を選んで質問への返事がYesだった場合、青木君は\(N-1\) 回の質問で \(i=A\) または \(j=B\) を満たす \((i,j)\) から正解を求める必要がありますが、これを確実に達成することはできないことが確認できます。 一方、良い質問をして返事がYesだった場合には以下のようにして答えを特定できます。

1. \(r=A\) または \(c=B\) を満たし、\(S_{r,c}=\) 1 を満たす \(r,c\) を一つ取る。
2. \(R=\{1,2,\ldots,N\}-\{A\}, C=\{1,2,\ldots,N\}-\{B\}\) とする。
3. 「\(x \in R, y \in C, x \neq r, y \neq c\) なる \(x,y\) を選んで \((x,y)\) として質問し、\(x,y\) を \(R,C\) から削除する」ということを \(N-2\) 回繰り返す。
4. この時点で \((i,j)\) の候補は 2か所以下なので、\(1\) 回質問をして特定する。

良い質問の返事がNoだった場合、\(i=A\) または \(j=B\) を除く \((N-1)^2\) 通りの \((i,j)\) から \(N-1\) 回で特定することになります。まだ質問に使っていない \(i',j'\) の集合を \(R,C\) とすると、\(x \in R, y \in C\) なる \((x,y)\) を質問に使う場合は同様に「( \(r=x\) かつ \(c\in C\) ) または( \(r \in R\) かつ \(c=y\) )」であるような良い選び方をする必要があります。

\(i',j'\) の重複なく良い選び方を \(N-2\) 回行える場合は答えがYes です。仮に \(N-2\) 回の質問への返事がすべてNoだった場合、残りの \(i,j\) の候補 \(i_1,i_2,j_1,j_2\) に対し \((i',j')=(i_1,A), (B, j_1)(A,B\)はすでに使った \(i',j')\) とすることで正解できるためです。

逆に \(N-2\) 回未満しか行えない場合の答えは No になることを証明します。返事がすべてNoだった場合に行う初めの \(N-1\) 回の質問の列を考えます。\(N-1\) 回の質問で使われていない \(i', j'\) の集合を \(R, C\) としたとき、任意の \(x \in R, y \in C\) について \(S_{x,y}=\)1 とできます。なぜなら、\(S_{x,y}=\)0 を満たす \(x,y\) が存在する場合は \(N-1\) 回の質問に含まれる良い質問でないもののうち最初のものを、 \(x,y\) を巻き込んだ良い質問に変えても損をしないためです。また、良い質問が高々 \(N-3\) 回しか行えないことを考えると \(|R|+|C| \geq 4\) かつ任意の \(x \in R, y \in C\) について \(S_{x,y}=\)1 となりますが、この場合に \(1\) 回の質問で \(i,j\) を特定することができないため、答えが No になります。

良い選び方を \(N-2\) 回できるかどうかの判定方法を考えます。\(2N\) 頂点の無向グラフであって、各 \(1 \leq i,j \leq N\) に対して \(S_{i,j} =\) 0 のときかつそのときに限り \(i, N+j\) に辺が貼られているもの、すなわち各頂点が \(i',j'\) に対応する二部グラフを考えます。もしこのグラフの無閉路部分グラフであって辺数 \(N-2\) のものが存在する場合、葉にあたる頂点と適当に余ったもう片側の頂点に対応する \((i',j')\) を選び続けることで \(N-2\) 回良い操作ができます。もしどのように \(N-2\) 本の辺を選んでも閉路が発生する場合、その閉路において操作をしようとすると同時に \(2\) 本以上の辺を消してしまうことになり、\(N-2\) 回の操作ができないということになります。
グラフの無閉路部分グラフが最大で何本の辺を含むかは貪欲に判定できるため、本問を \(\mathrm{O}(N^2)\) で解けました。