TOI10: TOI Raider

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int, int> tpp;

const int N = 97;
const int M = 100;
const int S = 2520;

int dirR[6] = {-1, -1, 0, 0, 1, 1};
int dirCEven[6] = {-1, 0, -1, 1, -1, 0};
int dirCOdd[6] = {1, 0, -1, 1, 1, 0};
int board[N][M], row, col;
bool visited[S][N][M];

bool isInBoard(int r, int c){
    return r >= 0 && r < row && c >= 0 && c < col;
}

int main(){

    scanf("%d%d", &row, &col);
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            scanf("%d", &board[i][j]);
        }
    }

    queue<tpp> que;
    for(int i = ((row - 1) >> 1) - 1; i <= ((row - 1) >> 1) + 1; ++i){
        if(board[i][0] == 1){
            visited[1][i][0] = true;
            que.emplace(i, 0, 1, 1);
        }
    }
    while(!que.empty()){
        int ur = get<0>(que.front());
        int uc = get<1>(que.front());
        int s = get<2>(que.front());
        int dist = get<3>(que.front());
        que.pop();
        if(ur == ((row - 1) >> 1) && uc == col - 1){
            cout << dist;
            return 0;
        }
        int vs = (s + 1) % S;
        bool isEven = (ur + 1) % 2 == 0;
        for(int d = 0; d < 6; ++d){
            int vr = ur + dirR[d];
            int vc = uc + (isEven ? dirCEven[d] : dirCOdd[d]);
            if(isInBoard(vr, vc) && !visited[vs][vr][vc] && board[vr][vc] != 0 && vs % board[vr][vc] == 0){
                visited[vs][vr][vc] = true;
                que.emplace(vr, vc, vs, dist + 1);
            }
        }
    }
    cout << "Impossible";

    return 0;
}