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[]={-,};

 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< || tmp.x>=n || tmp.y< || tmp.y>=m) return ;

     else return ;

 }

 int bfs(){

     queue<point> Q;

     sstart.x=x1;sstart.y=y11;sstart.time=;map[x1][y11]|=;

     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%==){

             if (!(map[pre.x][pre.y]&)){  //上下

                 for (int i=;i<;i++){

                     point next;

                     next.x=pre.x+change[i];

                     next.y=pre.y;

                     next.time=pre.time+;

                     if (check(next) && !((int)map[next.x][next.y]&)){

                         Q.push(next);

                         map[next.x][next.y]|=;

                     }

                 }

             }

             if (map[pre.x][pre.y]&){  //左右

                 for (int i=;i<;i++){

                     point next;

                     next.x=pre.x;

                     next.y=pre.y+change[i];

                     next.time=pre.time+;

                     if (check(next) && !((int)map[next.x][next.y]&)){

                         Q.push(next);

                         map[next.x][next.y]|=;

                     }

                 }

             }

         }

         else{

             if (!(map[pre.x][pre.y]&)){  //左右

                 for (int i=;i<;i++){

                     point next;

                     next.x=pre.x;

                     next.y=pre.y+change[i];

                     next.time=pre.time+;

                     if (check(next) && !((int)map[next.x][next.y]&)){

                         Q.push(next);

                         map[next.x][next.y]|=;

                     }

                 }

             }

             if (map[pre.x][pre.y]&){  //上下

                 for (int i=;i<;i++){

                     point next;

                     next.x=pre.x+change[i];

                     next.y=pre.y;

                     next.time=pre.time+;

                     if (check(next) && !((int)map[next.x][next.y]&)){

                         Q.push(next);

                         map[next.x][next.y]|=;

                     }

                 }

             }

         }

     }

     return -;

 }

 int main(){

     int t;

     char xx;

     cin >> t;

     while (t--){

         cin >> n >> m;

         for (int i=;i<n;i++) map[i].clear();

         for (int i=;i<n;i++){

             for (int j=;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 ;

 }

巴特西

zoj4020 Traffic Light（bfs+状态压缩）

最新文章

热门文章