| ||||||||||
| 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