Java, loop through 2d array in any direction

问题:

I'm trying to shift elements in an 2d array in any direction specified. By shift I mean, if left is pressed, each element of the array is moved as far to the left as it can.

so this (0 indicated an empty space),

1 0 2 0
0 3 0 1
1 0 6 9
1 0 0 0

would become

1 2 0 0
3 1 0 0
1 6 9 0
1 0 0 0

This is sudo code of what I have for if 'up' is pressed;

for col = 0 to SIZE
   for i = 0 to SIZE - 1
      if array[i][col] == 0
         for j = i to SIZE
            if array[j][col] != 0
               array[i][col] = array[row][j]
               array[j][col] = 0
               break

The actual code is a longer (ie. a check for two identical elements that collide) and I don't want to have 4 copies of this section of code (up, down, left, right), but I can't figure out how to do it any other way.

回答1:

What if you made a new array of the same length, and copied the elements into there? Then you would only have to iterate over your array once, making it O(n):

//This would be your array
int[] things = new int[]{1,23,4,54,234,54,1};

//Create a new array that is the same length
int[] shiftedThings = new int[things.length];

//These are for our loop
int start;
int end;

//If its an up shift
if(shiftUp){
    //Copy the last element into the first for an up shift
    shiftedThings[0] = things[things.length-1];

    //Start from the 2nd element, since we've already copied over the first
    start = 1;
    end = shiftedThings.length;
}   
else{
     //Copy the first element to the end for a down shift
     shiftedThings[shiftedThings.length-1] = things[0];

     start = 0;

     //End at 1 element before the end, since we've already copied over the last element
     end = shiftedThings.length-1;
} 

while(start < end){
    if(shiftUp)
        shiftedThings[index] = things[index-1];
    else
        shiftedThings[index] = things[index+1];
    start++;
}

//shiftedElements is now ready to be printed or returned or ...

---

There's probably a more elegant solution than this.

---

Edit: I didn't realize that you were talking about a 2D array until you edited your question. You could adapt this for your needs.

回答2:

While it is technically possible to cover all these shifting operations with the same methods, it's probably not as easy to understand (and not as efficient) as creating a dedicated method for each direction.

On the one hand, this is humbling and shattering for a real programmer, but on the other hand ... hey, you can be sure that there will never-ever be more than these four directions.

Or... well, diagonals, maybe? ;-)

public class ArrayShiftTest
{
    public static void main(String[] args)
    {
        int array[][] = new int[][]
        {
            { 1, 0, 2, 0 },
            { 0, 3, 0, 1 },
            { 1, 0, 6, 9 },
            { 1, 0, 0, 0 },
        };

        System.out.println("Original");
        print(array);

        System.out.println("Left");
        int arrayL[][] = clone(array);
        shift(arrayL,  0, -1);
        print(arrayL);

        System.out.println("Right");
        int arrayR[][] = clone(array);
        shift(arrayR,  0,  1);
        print(arrayR);

        System.out.println("Up");
        int arrayU[][] = clone(array);
        shift(arrayU, -1,  0);
        print(arrayU);

        System.out.println("Down");
        int arrayD[][] = clone(array);
        shift(arrayD,  1,  0);
        print(arrayD);

        // Bonus :-) :

        System.out.println("Left Up");
        int arrayLU[][] = clone(array);
        shift(arrayLU,  -1, -1);
        print(arrayLU);

        System.out.println("Right Up");
        int arrayRU[][] = clone(array);
        shift(arrayRU,  -1,  1);
        print(arrayRU);

        System.out.println("Left Down");
        int arrayLD[][] = clone(array);
        shift(arrayLD,   1, -1);
        print(arrayLD);

        System.out.println("Right Down");
        int arrayRD[][] = clone(array);
        shift(arrayRD,   1,  1);
        print(arrayRD);

    }

    private static void shift(int array[][], int dr, int dc)
    {
        boolean shifted = true;
        while (shifted)
        {
            shifted = false;
            for (int r=0; r<array.length; r++)
            {
                for (int c=0; c<array[r].length; c++)
                {
                    if (array[r][c] != 0)
                    {
                        shifted |= shift(array, r, c, dr, dc);
                    }
                }
            }
        }
    }

    private static boolean shift(int[][] array, int r, int c, int dr, int dc)
    {
        int value = array[r][c];
        array[r][c] = 0;
        int cr = r;
        int cc = c;
        while (isValid(array, cr, cc))
        {
            int tr = cr + dr;
            int tc = cc + dc;
            if (!isValid(array, tr, tc) || array[tr][tc] != 0)
            {
                break;
            }
            cr = tr;
            cc = tc;
        }
        array[cr][cc] = value;
        return cr != r || cc != c;
    }

    private static boolean isValid(int array[][], int r, int c)
    {
        return r>=0 && r<array.length && c>=0 && c<array[r].length;
    }

    private static int[][] clone(int array[][])
    {
        int result[][] = array.clone();
        for (int r=0; r<array.length; r++)
        {
            result[r] = array[r].clone();
        }
        return result;
    }

    private static void print(int array[][])
    {
        for (int r=0; r<array.length; r++)
        {
            for (int c=0; c<array[r].length; c++)
            {
                System.out.printf("%3d", array[r][c]);
            }
            System.out.println("");
        }
    }
}