Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
4.0 kB
3
Indexable
Never
int map[30][30];
int visit[30][30];
int visit2[30][30][4];
int q1[2000];
int q[500000];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int n;
int ans;
int t1, t2;
 
void init(int N, int mMap[][30]){
    n = N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            map[i][j] = mMap[i][j];
            visit[i][j] = 0;
        }
    }
    t1 = t2 = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                visit2[i][j][k] = 0;
            }
        }
    }
}
 
void BFS1(int start_r, int start_c, int r_row, int r_col, int t){
    visit[r_row][r_col] = t;
    int front = 0, rear = 0;
    q1[front++] = start_r;
    q1[front++] = start_c;
    visit[start_r][start_c] = t;
     
    while(front != rear){
        int now_r = q1[rear++];
        int now_c = q1[rear++];
         
        for (int i = 0; i < 4; i++)
        {
            int next_r = now_r +dx[i];
            int next_c = now_c +dy[i];
 
            if(next_r >= 0 && next_r < n && next_c > 0 && next_c < n)
                if(map[next_r][next_c] == 0 && visit[next_r][next_c] != t){
                    visit[next_r][next_c] = t;
                    q1[front++] = next_r;
                    q1[front++] = next_c;
                }
        }
    }
}
 
void BFS2(int r_row, int r_col, int g_row, int g_col, int p_row, int p_col, int dir){
    int front = 0, rear = 0, step = 0;
    q[front++] = r_row;
    q[front++] = r_col;
    q[front++] = p_row;
    q[front++] = p_col;
    q[front++] = step;
    visit2[r_row][r_col][dir] = t2;
    while(front != rear){
        int nowR_r = q[rear++];
        int nowR_c = q[rear++];
        int nowP_r = q[rear++];
        int nowP_c = q[rear++];
        int nowstep = q[rear++];
         
        if(nowR_r == g_row && nowR_c == g_col){
            ans = nowstep;
            break;
        }
        t1++;
        BFS1(nowP_r, nowP_c, nowR_r, nowR_c, t1);
         
        if(visit[nowR_r-1][nowR_c] == t1 && map[nowR_r+1][nowR_c] == 0 && visit2[nowR_r+1][nowR_c][0] != t2 ){
            visit2[nowR_r+1][nowR_c][0] = t2;
            q[front++] = nowR_r+1;
            q[front++] = nowR_c;
            q[front++] = nowR_r;
            q[front++] = nowR_c;
            q[front++] = nowstep+1;
                 
        }
         
        if(visit[nowR_r+1][nowR_c] == t1  && map[nowR_r-1][nowR_c] == 0 && visit2[nowR_r-1][nowR_c][2] != t2){
            visit2[nowR_r-1][nowR_c][2] = t2;
            q[front++] = nowR_r-1;
            q[front++] = nowR_c;
            q[front++] = nowR_r;
            q[front++] = nowR_c;
            q[front++] = nowstep+1;
                 
        }
         
        if(visit[nowR_r][nowR_c+1] == t1  && map[nowR_r][nowR_c-1] == 0 && visit2[nowR_r][nowR_c-1][1] != t2 ){
            visit2[nowR_r][nowR_c-1][1] = t2;
            q[front++] = nowR_r;
            q[front++] = nowR_c-1;
            q[front++] = nowR_r;
            q[front++] = nowR_c;
            q[front++] = nowstep+1;
            }
         
        if(visit[nowR_r][nowR_c-1] == t1  && map[nowR_r][nowR_c+1] == 0 && visit2[nowR_r][nowR_c+1][3] != t2 ){
            visit2[nowR_r][nowR_c+1][3] = t2;
            q[front++] = nowR_r;
            q[front++] = nowR_c+1;
            q[front++] = nowR_r;
            q[front++] = nowR_c;
            q[front++] = nowstep+1;     
        }
    }
}
 
int push(int mRockR, int mRockC, int mDir, int mGoalR, int mGoalC){
    ans = 0;
    int p_row,p_col;
    p_row = mRockR, p_col= mRockC;
    if(mDir == 0){
        --p_row;
    } else if(mDir == 1){
        ++p_col;
    } else if(mDir == 2){
        ++p_row;
    } else if(mDir == 3){
        --p_col;
    }
    t2++;
    BFS2(mRockR, mRockC, mGoalR, mGoalC, p_row,p_col, mDir);
 
    return ans;
}
Leave a Comment