Алгоритм заполнения Zig-zag?

Question

Как сделать алгоритм зигзага заполнить сетку любого размера, как показано на рисунке ниже?

Вот мой алгоритм, который не работает. (Вместо этого, начиная с нижнего левого и верхнего правого угла):

x1 = 0; 
y1 = grid_h-1; 
var a = 0; 
put(x1,y1); 

while(!((x1 = grid_w-1) and (y1 = 0))) { //If it isn't at the top right corner 
    if a = 2 { 
     x1 += 1; 
     put(x1,y1); 
     while(x1 != grid_w-1) { //While x1 isn't at the right 
      //Go diagonally down 
      x1 += 1; 
      y1 += 1; 
      put(x1,y1); 
     } 
     y1 -= 1; 
     put(x1,y1); 
     while(y1 != 0) { //While y1 isn't at the top 
      //Go diagonally up 
      x1 -= 1; 
      y1 -= 1; 
      put(x1,y1); 
     } 
    } else if a = 1 { 
     while(x1 != grid_w-1) { //While x1 isn't at the right 
      //Go diagonally down 
      x1 += 1; 
      y1 += 1; 
      put(x1,y1); 
     } 
     y1 -= 1; 
     put(x1,y1); 
     while(y1 != 0) { //While y1 isn't at the top 
      //Go diagonally up 
      x1 -= 1; 
      y1 -= 1; 
      put(x1,y1); 
     } 
     x1 += 1; 
     put(x1,y1); 
    } else { 
     y1 -= 1; 
     if (y1 = 0) { a = 1; } //At top? 
     put(x1,y1); 
     while(y1 != grid_h-1) { //While y1 isn't at the bottom 
      //Go diagonally down 
      x1 += 1; 
      y1 += 1; 
      put(x1,y1); 
     } 

     x1 += 1; 
     put(x1,y1); 
     while(x1 != 0) { //While x1 isn't at the left 
      //Go diagonally up 
      x1 -= 1; 
      y1 -= 1; 
      put(x1,y1); 
      if (y1 = 0) { a = 2; } //At top? 
     } 
    } 
} 

Простой способ сделать это?

Answer 1

Ключ наблюдения здесь является то, что вы идете на северо-восток, когда Manhattan distance в верхний левый квадрат нечетно и юго-запад в противном случае.

Конечно, вы должны рассмотреть возможность удара по одному из краев. Например, когда вы идете на юго-запад и попадаете на нижний или южный край, вместо этого вы двигаетесь на восток; когда вы нажмете левый или западный край, вы двигаетесь на юг. Вы можете либо поймать три случая (южный край, западный край, безудержное движение), либо вы можете перемещать и корректировать свое положение, когда вы выходите за пределы.

После того, как вы нанесли удар, ваше новое положение должно оставить вас в другом направлении. То есть, каждая коррекция включает нечетное число шагов. (Шаги здесь - расстояние Манхэттена между точкой, в которой вы попали, и точкой, в которой вы оказались.)

Если ваш алгоритм зигзагографа работает правильно, вы в конечном итоге будете посещать каждую ячейку один раз. То есть вы делаете H   ×   ж движется, где ч и ш являются высота и ширина. Вы можете использовать это как критерий завершения, а не проверять, находитесь ли вы в последнем квадрате.

Вот пример кода для этого решения. Дополнительный логический параметр down определяет, находится ли первый шаг вниз или слева.

function zigzag(width, height, down) { 
    var x = 0; 
    var y = 0; 
    var n = width * height; 

    if (down === undefined) down = false; 

    while (n--) { 
     var even = ((x + y) % 2 == 0); 

     put(x, y); 

     if (even == down) {    // walk southwest 
      x--; 
      y++; 

      if (y == height) { 
       y--; x += 2; 
      } 
      if (x < 0) x = 0; 
     } else {      // walk northeast 
      x++; 
      y--; 

      if (x == width) { 
       x--; y += 2; 
      } 
      if (y < 0) y = 0; 
     } 
    } 

    return res; 
} 

Answer 2

Вот решение, злоупотребляющее if-утверждениями.

x1 = 0; 
y1 = 0; 
put(x1,y1); 

var a = 0; 
while(!((x1 = grid_w-1) and (y1 = grid_h-1))) { 
    switch(a) { //Down, Right-Up, Right, Left-Down 
     case 0: y1++; break; 
     case 1: x1++;y1--; break; 
     case 2: x1++; break; 
     case 3: x1--;y1++; break; 
    } 
    put(x1,y1); 
    if (a = 2) { //If moved right. 
     if (x1 = grid_w-1) or (y1 = 0) { //If at the right or top edge. Go left-down. 
      a = 3 
     } else if (y1 = grid_h-1) { //At bottom edge. Go right-up. 
      a = 1 
     } 
    } else if (y1 = 0) { ///At top edge. 
     if (x1 = grid_w-1) { //If at the right corner. Go down. 
      a = 0; 
     } else { //Go right. 
      a = 2; 
     } 
    } else if (a = 3) { ///If moved left-down. 
     if (y1 = grid_h-1) { //At bottom n edge. Go right. 
      a = 2 
     } else if (x1 = 0) { //At left edge and not bottom. Go down. 
      a = 0 
     } 
    } else if (a = 0) { //If moved down. 
     if (x1 = 0) { //If at the left corner. Go right-up. 
      a = 1 
     } else if (x1 = grid_w-1) { //If at the right corner. Go left-down. 
      a = 3 
     } else { //Go right 
      a = 2 
     } 
    } else if (a = 1) { //If right-up. 
     if (x1 = grid_w-1) { //If at the right corner. 
      if (a = 2) { //If moved right. Go left-down. 
       a = 3 
      } else { //Go down. 
       a = 0 
      } 
     } 
    } 
} 

Не работает хорошо, если один из размера 1.

Answer 3

В принципе, мы можем использовать диаграмму состояний вместе с рекурсией, чтобы решить эту проблему.

permitted_directions = { 
"start":["down", "side"], 
"down":["north_east", "south_west"], 
"north_east":["north_east", "side","down"], 
"side":["north_east", "south_west"], 
"south_west":["south_west","down", "side"] 
} 

def is_possible(x, y, pos): 
    if pos == "down": 
     if x+1 < row and y >=0 and y < col: 
      return (True, x+1, y) 
    if pos == "side": 
     if x >= 0 and x < row and y+1 >=0 and y+1 < col: 
      return (True, x, y+1) 
    if pos == "north_east": 
     if x-1 >= 0 and x-1 < row and y+1 >= 0 and y+1 < col: 
      return (True, x-1, y+1) 
    if pos == "south_west": 
     if x+1 >= 0 and x+1 < row and y-1 >= 0 and y-1 < col: 
      return (True, x+1, y-1) 
    return (False, 0, 0) 

def fill_the_grid(grid, x, y, position, prev): 
    grid[x][y] = prev 
    prev = (x, y) 
    for pos in permitted_directions[position]: 
     possible, p, q = is_possible(x, y, pos) 
     if possible: 
      return fill_the_grid(grid, p, q, pos, prev) 
    return grid