Threaded Mode | Linear Mode

***drdebcol*** · 03-02-2010, 11:00 PM

This is an interesting task. You can solve non-recursively, but i decided to use recursion (it is linear recursion).
You need to fill square matrix with numbers from 1 to n*n.
Square matrix has n*n fields so it's length equals to it's height.
The way of filling is almost the same as spiral way of filling, which you have here in this discussion :
http://www.pro9ramming.com/another-reque...t-622.html
Here is the example how should you fill for matrix 3x3 :
[Image: 43379_spiral2matrixfill3x3.jpg]

As you can see it is the same as spiral, but only for cases 2x2 and 3x3, for 4x4 you can see on the picture :
[Image: 43380_spiral2matrixfill4x4.jpg]

So it is basically going over the matrix to the point (n,1) and up to (n-1,1) and then turn right to the end and than up . . .
For 6x6 you can see it :
[Image: 43381_spiral2matrixfill6x6.jpg]

As you can see for cases when n is even we have the situation that the last number (n*n) is always in field (2,1) and when n is odd then it ends in (2,n-1).
Also to define mathematically when you have matrix field (x,y), x axis is vertical and y is horizontal.
Input is ordinary unsigned integer (not zero) and output is a matrix n*n filled in this way shown.
Solution
Well i defined a matrix starting from 0 to n+1.
And i filled it around with ones and n the middle with zeros.
Like this :
[Image: 43389_matrixfillaround.jpg]

That is example for n=1 and 2 and 3 and 4 and 5.
And than go with recursion from point or field (1,1) to the right until you find a field with something bigger than zero and than down and than left and than up and so on.
The most important part is sequence right>>down>>left>>up.
You can try it on a piece of paper and you'll see that it actually fills matrix in this way.
I have solved it in Pascal :

Code:

program matrix_fill;

uses wincrt;

var

a:array[0..50,0..50] of integer;

i,j,n,br:integer;

procedure fill_matrix(x,y:integer);

begin

  br:=br+1;

  if a[x,y+1]=0 then

    begin

      a[x,y+1]:=br;

      fill_matrix(x,y+1);

    end

    else

     if a[x+1,y]=0 then

       begin

        a[x+1,y]:=br;

        fill_matrix(x+1,y);

       end

       else

        if a[x,y-1]=0 then

         begin

          a[x,y-1]:=br;

          fill_matrix(x,y-1);

         end

         else

          if a[x-1,y]=0 then

           begin

            a[x-1,y]:=br;

            fill_matrix(x-1,y);

           end;

end;

begin

 br:=1;

 readln(n);

 for i:=0 to n+1 do

   for j:= 0 to n+1 do

     a[i,j]:=1;

 for i:=1 to n do

   for j:=1 to n do

     a[i,j]:=0;

     a[1,1]:=1;

     fill_matrix(1,1);

 for i:=1 to n do

   begin

     for j:=1 to n do

       write(a[i,j],' ');

     writeln;

   end;

end.

***Back_track*** · 03-05-2010, 05:15 AM

This section is starting to become my favorite, every time i visit here i learn something mathematical

***l3g1sl4tor*** · 03-05-2010, 05:17 AM

this ain't only very interesting math problem, it is also common programing problem... almost in every task about 2d arrays you will be needed to initialize matrix first! Smile

***drdebcol*** · 03-05-2010, 06:22 AM

(03-05-2010 05:17 AM)l3g1sl4tor Wrote: this ain't only very interesting math problem, it is also common programing problem... almost in every task about 2d arrays you will be needed to initialize matrix first!

Yeah almost in every, but in certain tasks there are certain optimizations.
I have done it recursively but noticing interesting row of doing things in this task. It can be done non recursively with few for loops, but that is just a not so interesting way, it is better to be a bit more complicated !