El enunciado es muy vago en su descripción. No sé que hay que hacer.

De entrada se me plantea una duda:
Si la matriz ordenada no puede repetir ningún número puede que sea de menor tamaño que la matriz original. Siendo así:
¿La matriz ordenada debe ser la misma matriz original? Si la matriz original es estática, eso es definida del tipo T[dimY][dimX], no se puede reducir su tamaño. ¿Cómo se marcan las casillas vacías? ¿Cómo se distribuye la información en la matriz?
Si la matriz original es dinámica se pueden reducir sus dimensiones pero de nuevo aparece el problema de como se distribuye el sistema si no se pueden cuadrar las dimensiones (número impar de elementos).

Jaja, sí, pero creo que la idea de NOB2014 no iba por ahí 

A ver, esto es porqué no me gusta lo de C/C++, la gente tiende a mezclarlos.
C estándar, sin extensiones de compiladores ni otras historias, no tiene sobrecargas; sus archivos de cabecera son los terminados en .h; no necesita castings en los punteros a void. Mientras C++ es todo lo contrario en estos puntos.

Yo he hecho el siguiente código que, a diferencia del tuyo, destruye la variable original.

#include <stdio.h>
#include <math.h>
 
int main() {
    unsigned num = -12345;
    unsigned resultado;
    int d = 1;
 
    while(num) {
        resultado ^= d * (num & 1);
        num >>= 1;
        d <<= 1;
    }
    printf("El número buscado es %i", resultado);
 
    return 0;
}

Ah, pues lo primero que debes hacer es avisar al usuario si se excede en las dimensiones, o son muy pequeñas (imagínate que pone 0 o menor a 0).

Después con bucles anidados haces (te lo voy a dejar en seudocódigo porqué es muy fácil.
Similar para conseguir el número de 0s para las columnas.
Para toda la tabla es

Te recomiendo te pases por aquí:
https://www.youtube.com/watch?v=kjYKBEUB0y0

Se refiere a las cabeceras stdio, math, stdlib, etc.
Mientras en C son stdio.h, math.h, stdlib.h, ...
En C++ son cstdio, cmath, cstdlib, ...

Recuerda que los números naturales empiezan en el 1, sino son enteros.

---

Ups, vale, que existen las dos formas: la que incluye 0 en el conjunto de los naturales y la que no incluye el 0 en el conjunto de los naturales. No he dicho nada. 

Oh, que bueno!
El primero que veo que incuye todas las cabeceras correctas de C++. 

Pero fallas en la definicion de la tabla. No debería ser
porque así el tamaño lo decides tu, no el usuario: si este usa números más grandes te buscará para que le devuelvas el dinero.