Your question makes a dangerous assumption. It's assuming that generality is the opposite of simplicity.
Since this question, in part, deals with semantics, let's define the terms.
General - applicable to a variety of situations, robust, useful
Simple - easy to understand, obvious, having few parts
These are actually two axes. The opposite of general is specific. The opposite of simple is complicated (not complex).
The best solutions in programming are both Simple & General.
Using a language well is the very art of making the general solution a simple one.
Since you're asking about something subjective, here's my view. Your solution to the problem is general, but it's not simple. Other solutions, like those requiring intuition about 0 or 1 being in the matrix are also not simple. In fact, any solution that is described in terms of the algorithm to find the solution is not simple.
This is a mistake many programmers (most?) make. They decompose the problem in their heads, but don't share that decomposition with the code. In this question, the first thing one should do to make it obvious to a new reader of the code is "What are we doing"? Are we turning rows in numbers? Are we navigating a grid of bits? Are we reasoning about matrix properties? Make it explicit. This prevents a new reader from having to reverse engineer the ideas every time he examines code.
Your solution is comparing rows.
You can add to the code the notion that you're comparing rows before you need to worry about whether this is NxN or NxM. Those details are handled in how you compare rows, but at that point the problem has changed from a matrix into two rows (a simpler problem). Then later, even comparing two rows simplifies to comparing two bits in those rows.
Fluent interfaces, declarative code, etc, all try to address these issues. Compilers are getting better and better at inlining efficiency (processors too). The days of needing to write a clever low-level loop algorithm for efficiency are going away.
Consider code like this:
Row smallest = matrix.FirstRow
for each Row r in matrix.rows
if r < smallest
smallest = r
Object orientation allows all sorts of state to be stored in a Row object. this allows for the tricks in your solution to be embedded in the Row object (including your 'which row am I on' trick; the < operator can be overloaded to do things like column 0 or 1 compares on that row). The efficiency can be made the same, while still making it simple (obvious) what's going on.
Even before we talk about implementing the 'search' for the best row, there's a bunch of information in the setup of the matrix itself (sorted rows, etc.) In fact, if this were C#, I'd simply write the search as matrix.Rows.Min() and create a representation of the Matrix and Rows that takes these assumptions into its definition. This makes those invariants setup by the question implicit in the code instead of just 'known' by the tricky assumptions the looping algorithm can make.
Once you do that, you'll see all sorts of neat things happen. The tricks people were saying about just looking for the 0000, or 0001 will be obvious because you'll be able to optimize the structure of the matrix itself (think array of NumberOf0's[RowNumber]). That last bit is 'getting complicated' but at least it's complexity in representing the input data and not yet searching for the solution.
Decomposition gives both generality and power, while keeping things simple.