zoj4020 Traffic Light（bfs+状态压缩）

题意：每个点有两种状态，0/1，0表示只能上下方向走，1表示只能左右方向走。每走一步整个图的状态改变一次（即0->1,1->0）。

数据范围：n,m<=1e15

开始迷之因为数组太大编译不过（但是有的人过了就不是很懂orz）。强制状态压缩，将map用vector存储。然后对于每个点奇数次访问用2标记，偶数次访问用4标记。

利用int是8字节的特点，最后一位记录map，前面两位记录访问状态。

若奇数次访问过后，map[i][j] |= 2；若偶数次访问过后，map[i][j] |= 4。

这种状压真的强势。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 100005
using namespace std;
const int change[2]={-1,1};
struct point{
    int x,y;
    int time;
}sstart;
int n,m;
int x1,x2,y11,y2;
vector<int>map[maxn];
int check(point tmp){
    if (tmp.x<0 || tmp.x>=n || tmp.y<0 || tmp.y>=m) return 0;
    else return 1;
}
int bfs(){
    queue<point> Q;
    sstart.x=x1;sstart.y=y11;sstart.time=0;map[x1][y11]|=4;
    Q.push(sstart);
    while (!Q.empty()){
        point pre=Q.front();
        Q.pop();
        if (pre.x==x2 && pre.y==y2) return pre.time;
        if (pre.time%2==0){
            if (!(map[pre.x][pre.y]&1)){  //上下 
                for (int i=0;i<2;i++){
                    point next;
                    next.x=pre.x+change[i];
                    next.y=pre.y;
                    next.time=pre.time+1;
                    if (check(next) && !((int)map[next.x][next.y]&4)){
                        Q.push(next);
                        map[next.x][next.y]|=4;
                    }
                }
            }
            if (map[pre.x][pre.y]&1){  //左右 
                for (int i=0;i<2;i++){
                    point next;
                    next.x=pre.x;
                    next.y=pre.y+change[i];
                    next.time=pre.time+1;
                    if (check(next) && !((int)map[next.x][next.y]&4)){
                        Q.push(next);
                        map[next.x][next.y]|=4;
                    }
                }
            }
        }
        else{
            if (!(map[pre.x][pre.y]&1)){  //左右 
                for (int i=0;i<2;i++){
                    point next;
                    next.x=pre.x;
                    next.y=pre.y+change[i];
                    next.time=pre.time+1;
                    if (check(next) && !((int)map[next.x][next.y]&2)){
                        Q.push(next);
                        map[next.x][next.y]|=2;
                    }
                }
            }
            if (map[pre.x][pre.y]&1){  //上下 
                for (int i=0;i<2;i++){
                    point next;
                    next.x=pre.x+change[i];
                    next.y=pre.y;
                    next.time=pre.time+1;
                    if (check(next) && !((int)map[next.x][next.y]&2)){
                        Q.push(next);
                        map[next.x][next.y]|=2;
                    }
                }
            }
        }
    } 
    return -1;
}
int main(){
    int t;
    char xx;
    cin >> t;
    while (t--){
        cin >> n >> m;
        for (int i=0;i<n;i++) map[i].clear();
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                cin >> xx;
                map[i].push_back(xx);
            }
            getchar();
        }
        cin >> x1 >> y11 >> x2 >> y2;
        x1--;y11--;x2--;y2--;
        int ans;
        ans=bfs();
        cout << ans << endl;
    }
    return 0;
}