Suponiendo que todos los elementos son enteros positivos. Sino se le puede hacer unos retoques podrias sumar todos los elementos de las filas o columnas y ver cual es esa suma.
Si una columna tiene todo cero, la suma de todos los elementos de esta columna tiene que dar cero. Si son todos uno la suma daria N.
La idea seria la siguiente:
Supongamos que tenemos una matriz NxN. entonces definimos una matriz N+1 X N+1
Código C:
Ver originalint matriz[N+1][N+1];
for(i=0;i< N ; i++)
for(j=0;j< N ; j++) {
matriz[i][N] += matriz[i][j];
matriz[N][j] += matriz[i][j];
}
Luegos comparas los elementos como te dije. Esto es lo mas rapido que se me ocurre por el momento. Solo se recorre una vez la matriz y podes determinar todas las columnas o filas que decis.
Saludos,
Espero que se entienda.