Untitled
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