#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());
    }
}

• Re:状压BFS，时隔两个半月，二刷1A留念 (2895) renhaijiao 2020-11-24 14:18:25