Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:状压BFS,时隔两个半月,二刷1A留念In Reply To:状压BFS,时隔两个半月,二刷1A留念 Posted by:vjubge4 at 2019-06-16 20:59:13 > #include<cstdio> > #include<cstring> > #include<algorithm> > #include<queue> > using namespace std; > const int oo = 0x3f3f3f3f; > int W, H; > int field[20][20]; > int sx, sy, ss; > int L, N; > int dx[] = {1, 0, -1, 0}; > int dy[] = {0, -1, 0, 1}; > int dist[20][20][1 << 14]; > struct P{ > int x, y, s; > }; > > bool Judge(int nx, int ny, int x, int y, int s){ > if(nx < 0 || nx >= H || ny <0 || ny >= W || field[nx][ny] == 1){ > return false; > } > for(int i = 0; i < L - 1; i ++){ > int mv = (s >> (2 * i)) & 3; > x = x + dx[mv]; > y = y + dy[mv]; > if(nx == x && ny == y){ > return false; > } > } > return true; > } > > int bfs(){ > memset(dist, oo, sizeof(dist)); > dist[sx][sy][ss] = 0; > queue<P> que; > que.push((P){sx, sy, ss}); > while(!que.empty()){ > P p = que.front(); > que.pop(); > if(p.x == 0 && p.y == 0){ > return dist[p.x][p.y][p.s]; > } > for(int i =0; i < 4; i ++){ > int nx = p.x + dx[i]; > int ny = p.y + dy[i]; > int ns = p.s; > if(Judge(nx, ny, p.x, p.y, p.s)){ > ns = (ns << 2) + (i + 2) % 4; > ns &= (1 << ((L - 1) * 2)) - 1; > if(dist[nx][ny][ns] > dist[p.x][p.y][p.s] + 1){ > dist[nx][ny][ns] = dist[p.x][p.y][p.s] + 1; > que.push((P){nx, ny, ns}); > } > } > } > } > return -1; > } > > int main(){ > int c = 0; > while(true){ > scanf("%d %d %d", &H, &W, &L); > if(H == 0 && W == 0 && L == 0){ > break; > } > memset(field, 0, sizeof(field)); > pair<int, int> arr[8]; > for(int i = 0; i < L; i ++){ > scanf("%d %d", &arr[i].first, &arr[i].second); > arr[i].first --; > arr[i].second --; > } > sx = arr[0].first; > sy = arr[0].second; > ss = 0; > for(int i = L - 1; i > 0; i --){ > ss <<= 2; > if(arr[i].second == arr[i - 1].second){ > if(arr[i].first == arr[i - 1].first + 1){ > ss += 0; > } else { > ss += 2; > } > } else { > if(arr[i].second == arr[i - 1].second - 1){ > ss += 1; > } else { > ss += 3; > } > } > } > scanf("%d", &N); > int a, b; > for(int i =0; i < N; i ++){ > scanf("%d %d", &a, &b); > field[a - 1][b - 1] = 1; > } > printf("Case %d: %d\n", ++c, bfs()); > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator