c++ - llenar - matriz caracol algoritmo en c

Imprimir matriz 2-D en espiral que se expande hacia la derecha desde el centro

Question

Tengo una garantía de ser una matriz cuadrada perfecta . Quiero comenzar en el centro de la matriz, en este caso sería la matrix[2][2] , sé cómo calcular el centro (int)(dimensions / 2) . Necesito dar salida al contenido de la matriz en este siguiente patrón de espiral hacia afuera . Por supuesto, el algoritmo debería funcionar con cualquier matriz cuadrada perfecta. No estaba seguro de si este algoritmo ya existía y no quería volver a inventar la rueda.

int dimensions / 2;
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

La salida para este ejemplo debe ser

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Answer 1

Como esto huele a tarea, entonces no hay código o respuesta directa, en cambio solo algunos consejos:

Puedes ver esto como un problema de tortuga:

Deje m ser movimiento por 1 celda y r gire 90 grados en la dirección de la espiral (CW o CCW). luego, la espiral se puede codificar como una serie de comandos de tortuga que forman este patrón (desde el punto de inicio):

 m,r,m,r,
m,m,r,m,m,r,
m,m,m,r,m,m,m,r,
m,m,m,m,r,m,m,m,m,r,
m,m,m,m,m,r 

Como puede ver, comienza con 1x movimiento y luego gira después de dos repeticiones, cambia a 2x movimiento, después de 2 movimientos cambia a 3 veces movimiento, ... y así sucesivamente. Esto se puede hacer con pocos bucles for (o solo con uno con algunas iteraciones adecuadas y deteniéndose cuando se golpea el número de células de la matriz ... o se golpea la esquina del punto final)

Necesita manejar tamaños de matrices pares / impares

para los tamaños de matrices impares es el punto medio fácil. Para los tamaños pares, es un poco más complicado. si usa la rotación en CW, utilice el resultado de división redondeada hacia abajo para reducir a la mitad el tamaño y comience moviéndose hacia la derecha. (si necesita una espiral diferente, entonces necesita agregar +1 a x y / o y cambiar la dirección de inicio) para que la espiral permanezca centrada.

Entonces, si tienes una matriz de tamaño uniforme, el último movimiento es dos veces si obtienes un tamaño impar, entonces el último movimiento está ahí solo una vez (como en este ejemplo)

rotación

Tener la dirección almacenada como vector 2D. por ejemplo d=(+1,0) significa correcto. para rotar el vector 2D, simplemente intercambia coordenadas y niega un eje (lo que significa CW / CCW). Por ejemplo (x,y) -> (y,-x)

movimiento

Almacena la posición actual como vector 2D también. El movimiento simplemente le agrega un vector de dirección actual.

Diviértete resolviendo esto ...

Answer 2

Identifiquemos los patrones primero ...

Matriz cuadrada de tamaño par, ejemplo: 4x4

 07 > 08 > 09 > 10
^ v
06 (01)> 02 11
^ v v
05 < 04 < 03 12
v
[16]< 15 < 14 < 13
Starting Point: [2, 2] ~ [SIZE/2, SIZE/2]
Ending Point: [4, 1] ~ [SIZE, 1]
Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
+ 3 for Count = SIZE-1

Tamaño impar de matriz cuadrada, Ejemplo: 5x5

 21 > 22 > 23 > 24 >[25]
^
20 07 > 08 > 09 > 10
^ ^ v
19 06 (01)> 02 11
^ ^ v v
18 05 < 04 < 03 12
^ v
17 < 16 < 15 < 14 < 13
Starting Point: [2, 2] ~ [⌊SIZE/2⌋, ⌊SIZE/2⌋]
Ending Point: [1, 5] ~ [1, SIZE]
Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
+ 3 for Count = SIZE-1

Código en vivo

void print_spiral (int ** matrix, int size)
{
int x = 0; // current position; x
int y = 0; // current position; y
int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
int c = 0; // counter
int s = 1; // chain size
// starting point
x = ((int)floor(size/2.0))-1;
y = ((int)floor(size/2.0))-1;
for (int k=1; k<=(size-1); k++)
{
for (int j=0; j<(k<(size-1)?2:3); j++)
{
for (int i=0; i<s; i++)
{
std::cout << matrix[x][y] << " ";
c++;
switch (d)
{
case 0: y = y + 1; break;
case 1: x = x + 1; break;
case 2: y = y - 1; break;
case 3: x = x - 1; break;
}
}
d = (d+1)%4;
}
s = s + 1;
}
}

Answer 3

 int radius = 0;
int i = centerX;
int j = centerY;
Debug.Log("i=" + i + "; j=" + j);
++i;
radius += 2;
while ((i < dimm) && (i >= 0))
{
for (int c = j; j < c + radius; j++)
Debug.Log("i=" + i + "; j=" + j);
--j;
--i;
for (int c = i; i > c - radius + 1; i--)
Debug.Log("i=" + i + "; j=" + j);
if (i < 0)
break;
else
Debug.Log("i=" + i + "; j=" + j);
--j;
for (int c = j; j > c - radius; j--)
Debug.Log("i=" + i + "; j=" + j);
++i;
++j;
for (int c = i; i < c + radius; i++)
Debug.Log("i=" + i + "; j=" + j);
radius += 2;
}

Este Código generará índices de matrices cuadradas en sentido antihorario (dimm X dimm) del centro personalizado (CenterX, CenterY); y terminan, si salió del tamaño de la matriz.

Answer 4

bool IsIterationComplete(int iteration, int nCenter, std::vector<std::vector<bool>>& vVisited)
{
int nHigh = nCenter+iteration;
int nLow = nCenter-iteration;
//cout<<endl<<"High "<<nHigh<<"Low "<<nLow<<endl;
for(int i=nLow;i<=nHigh;i++)
{
if(!vVisited[nHigh][i] || !vVisited[nLow][i])
return false;
}
for(int i=nLow;i<=nHigh;i++)
{
if(!vVisited[i][nHigh] || !vVisited[i][nLow])
return false;
}
return true;
}
void PrintSpiral(std::vector<std::vector<int>>& vMat,std::vector<std::vector<bool>>& vVisited, int row, int col, int nCenter, int iteration)
{
cout<<vMat[row][col];
vVisited[row][col]=true;
if(row==0 && col==0)
return;
if(IsIterationComplete(iteration,nCenter,vVisited))
iteration++;
//cout<<endl<<"row "<<row<<" column "<<col<<"Iteration "<<iteration<<endl;
//left
if(col-1>=0 && !vVisited[row][col-1] && col-1>=nCenter-iteration)
{
cout<<"Left "<<endl;
PrintSpiral(vMat,vVisited,row,col-1,nCenter,iteration);
}
//Down
if((row+1)<vMat.size() && !vVisited[row+1][col] && row+1<=nCenter+iteration)
{
cout<<"Down "<<endl;
PrintSpiral(vMat,vVisited,row+1,col,nCenter,iteration);
}
//right
if((col+1)<vMat.size() && !vVisited[row][col+1] && col+1<=nCenter+iteration)
{
cout<<"Right "<<endl;
PrintSpiral(vMat,vVisited,row,col+1,nCenter,iteration);
}
//up
if(row-1>=0 && !vVisited[row-1][col] && row-1>=nCenter-iteration)
{
cout<<"Up "<<endl;
PrintSpiral(vMat,vVisited,row-1,col,nCenter,iteration);
}
}
int main (int argc, const char * argv[])
{
int nCount=1;
std::vector<std::vector<int>> vMat;
std::vector<std::vector<bool>> vVisited;
for(int i=0; i<7; i++)
{
std::vector<int> row;
std::vector<bool> visitedRow;
for(int j=0; j<7; j++)
{
row.push_back(nCount);
cout<<nCount<<''/t'';
nCount++;
visitedRow.push_back(false);
}
cout<<''/n'';
vMat.push_back(row);
vVisited.push_back(visitedRow);
}
cout<<''/n'';
PrintSpiral(vMat,vVisited,vMat.size()/2,vMat.size()/2,vMat.size()/2,0);
return 0;
}