题意：每个点有两种状态，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。

这种状压真的强势。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #define maxn 100005 8 using namespace std; 9 const int change[2]={-1,1}; 10 struct point{ 11 int x,y; 12 int time; 13 }sstart; 14 int n,m; 15 int x1,x2,y11,y2; 16 vector
           
            map[maxn]; 17 int check(point tmp){ 18 if (tmp.x<0 || tmp.x>=n || tmp.y<0 || tmp.y>=m) return 0; 19 else return 1; 20 } 21 int bfs(){ 22 queue
            
              Q; 23 sstart.x=x1;sstart.y=y11;sstart.time=0;map[x1][y11]|=4; 24 Q.push(sstart); 25 while (!Q.empty()){ 26 point pre=Q.front(); 27 Q.pop(); 28 if (pre.x==x2 && pre.y==y2) return pre.time; 29 if (pre.time%2==0){ 30 if (!(map[pre.x][pre.y]&1)){ //上下 31 for (int i=0;i<2;i++){ 32 point next; 33 next.x=pre.x+change[i]; 34 next.y=pre.y; 35 next.time=pre.time+1; 36 if (check(next) && !((int)map[next.x][next.y]&4)){ 37 Q.push(next); 38 map[next.x][next.y]|=4; 39 } 40 } 41 } 42 if (map[pre.x][pre.y]&1){ //左右 43 for (int i=0;i<2;i++){ 44 point next; 45 next.x=pre.x; 46 next.y=pre.y+change[i]; 47 next.time=pre.time+1; 48 if (check(next) && !((int)map[next.x][next.y]&4)){ 49 Q.push(next); 50 map[next.x][next.y]|=4; 51 } 52 } 53 } 54 } 55 else{ 56 if (!(map[pre.x][pre.y]&1)){ //左右 57 for (int i=0;i<2;i++){ 58 point next; 59 next.x=pre.x; 60 next.y=pre.y+change[i]; 61 next.time=pre.time+1; 62 if (check(next) && !((int)map[next.x][next.y]&2)){ 63 Q.push(next); 64 map[next.x][next.y]|=2; 65 } 66 } 67 } 68 if (map[pre.x][pre.y]&1){ //上下 69 for (int i=0;i<2;i++){ 70 point next; 71 next.x=pre.x+change[i]; 72 next.y=pre.y; 73 next.time=pre.time+1; 74 if (check(next) && !((int)map[next.x][next.y]&2)){ 75 Q.push(next); 76 map[next.x][next.y]|=2; 77 } 78 } 79 } 80 } 81 } 82 return -1; 83 } 84 int main(){ 85 int t; 86 char xx; 87 cin >> t; 88 while (t--){ 89 cin >> n >> m; 90 for (int i=0;i
             
              > xx; 94 map[i].push_back(xx); 95 } 96 getchar(); 97 } 98 cin >> x1 >> y11 >> x2 >> y2; 99 x1--;y11--;x2--;y2--;100 int ans;101 ans=bfs();102 cout << ans << endl;103 }104 return 0;105 }