Роллинг кости в спирали

Question

Учитывая размер сетки nxn, кубики помещаются в верхнем левом поле (1,1) с номером 6 вниз, 5 лицом (1,2) и 4 лицом (2 , 1). Кости будут катиться по спирали (по часовой стрелке), чтобы заполнить каждое поле числом (только один раз). Рассчитайте общую сумму напечатанных номеров. Визуальное представление ходов кости и номер печатается при п = 5 (результат = 81)

01 02 03 04 05 
16 17 18 19 06 
15 24 25 20 07 
14 23 22 21 08 
13 12 11 10 09 

6 5 1 2 6 
4 5 3 2 4 
1 1 3 1 1 
3 2 3 5 3 
6 5 1 2 6 

Это домашнее задание вопрос, но я не могу понять, как сделать это эффективно, не проходя через все возможных случаях. Если кто-то может дать мне решение и объяснение, это будет потрясающе (не требуется код, я хочу сделать это сам).

Answer 1

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

class Dice 
{ 
public: 
    Dice(); 
    int face_down(); 
    void roll_west(); 
    void roll_east(); 
    void roll_north(); 
    void roll_south(); 
    void set_initial_config(int face_down,int east,int north,int west,int south); 
    ~Dice(); 
private: 
    /// variables for your state etc 
}; 

Если вы реализуете Dice успешно, остальная работа будет простой симуляцией прокатки костей.

int roll(int n,int m){ // grid dimensions 

    std::vector<std::vector<bool> > visited(n,std::vector<bool>(m,0)); 

    int i=0,j=-1; 
    int dir=0; 
    bool dir_changed; 
    int dir_change_count=0; 
    int sum=0; 
    Dice d; 

    while(dir_change_count<4){ 

     dir_changed=0; 
     switch(dir){ 
      case 0: 
       if(j+1<m and !visited[i][j+1]){ 
        j++; 
        visited[i][j+1]=1; 
        d.roll_east(); 
       }else{ 
        dir_changed=1; 
        dir++; 
       } 
       break; 
      case 1: 
       if(i+1<n and !visited[i+1][j]){ 
        i++; 
        visited[i+1][j]=1; 
        d.roll_south(); 
       }else{ 
        dir_changed=1; 
        dir++; 
       } 
       break; 
      case 2: 
       if(j-1>=0 and !visited[i][j-1]){ 
        j--; 
        visited[i][j-1]=1; 
        d.roll_west(); 
       }else{ 
        dir_changed=1; 
        dir++; 
       } 
       break; 
      case 3: 
       if(i-1>=0 and !visited[i-1][j]){ 
        i--; 
        visited[i-1][j]=1; 
        d.roll_north(); 
       }else{ 
        dir_changed=1; 
        dir++; 
       } 
       break; 
     } 
     if(!dir_changed){ 
      sum+=d.face_down(); 
      dir_change_count=0; 
     }else{ 
      dir_change_count++; 
     } 
    } 

    return sum; 
}