ZOJ Problem Set - 4020 Traffic Light

题意

在道路上从a到b， 每一个十字路口都有红绿灯，红绿灯的状态有开关两种，每走一次变一下，在不同的状态可以往不同的方向走,求最短路径（和最短路径一个意思)

分析

本体的关键就是要知道经过一个点之后，一定不会再回来，因为回来的时候和现在红绿的状态一样，即回到远来的位置一定是偶数步，所以走回来就没有意义了。 所以怎么解这道题呢，当然是广搜，把所有能走到的节点加进去，最后如果搜不到就是“No Solution” ,否则输出时间

参考代码

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
const int maxn = 1e5+100;
int  State[maxn];
bool vis[maxn];
int n,m;
int X1,Y1,x2,y2;
struct T{
  int x,y,t;
  T(int xx,int yy,int tt):x(xx),y(yy),t(tt){}
};
int  bfs()
{
    queue<T> q;
    q.push(T(X1,Y1,0));
    vis[X1*m+Y1] = 1;
    while(!q.empty())
    {
        T a = q.front(); q.pop();
        if(a.x == x2&&a.y == y2)// 如果找到，返回到这个点的时间
            return a.t;
        int x = a.x,y = a.y,t = a.t;
        int s = (t&1?!State[x*m+y]:State[x*m+y]);// 判断奇数步和偶数步确定状态以确定 行进方向

        if(s)
        {
            for(int i = 2;i < 4; ++i)
            {
                int R = x + dr[0][i];
                int C = y + dr[1][i];
                if(R < n&&R >= 0&&C < m&&C >=0&&!vis[R*m+C])
                {
                    vis[R*m+C] = true;
                    q.push(T(R,C,t+1));// 注意时间要+1
                }
            }
        }
        else
        {
            for(int i = 0;i < 2; ++i)
            {
                int R = x + dr[0][i];
                int C = y + dr[1][i];
                if(R < n&&R >= 0&&C < m&&C >= 0&&!vis[R*m+C])
                {
                    vis[R*m+C] = true;
                    q.push(T(R,C,t+1));
                }
            }
        }
    }
    return -1;

}
int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(int i = 0;i < n; ++i)
        {
            for(int j = 0;j < m; ++j)
            {
               scanf("%d",&State[i*m+j]);
            }
        }
        scanf("%d %d %d %d",&X1,&Y1,&x2,&y2);
        X1--,Y1--,x2--,y2--;
        printf("%d\n",bfs());
    }

    return 0;
}