ZOJ 4020 Traffic Light

Traffic Light

Time Limit: 1 Second Memory Limit: 131072 KB

DreamGrid City is a city with $intersections arranged into a grid of rows and columns. The intersection on the -th row and the -th column can be described as, and two intersections and are connected by a road if .$

At each intersection stands a traffic light. A traffic light can only be in one of the two states: 0 and 1. If the traffic light at the intersection $is in state 0, one can only move from to or; If the traffic light is in state 1, one can only move from to or (of course, the destination must be another intersection in the city).$

BaoBao lives at the intersection $, and he wants to visit his best friend DreamGrid living at the intersection . After his departure, in each minute the following things will happen in order:$

BaoBao moves from his current intersection to another neighboring intersection along a road. As a law-abiding citizen, BaoBao has to obey the traffic light rules when moving.
Every traffic light changes its state. If a traffic light is in state 0, it will switch to state 1; If a traffic light is in state 1, it will switch to state 0.

As an energetic young man, BaoBao doesn't want to wait for the traffic lights, and he must move in each minute until he arrives at DreamGrid's house. Please tell BaoBao the shortest possible time he can move from $to to meet his friend, or tell him that this is impossible.$

Input

There are multiple test cases. The first line of the input contains an integer $, indicating the number of test cases. For each test case:$

The first line contains two integers $and (), indicating the size of the city.$

For the following $lines, the -th line contains integers (), where indicates the initial state of the traffic light at intersection .$

The next line contains four integers $,, and (,), indicating the starting intersection and the destination intersection.$

It's guaranteed that the sum of $over all test cases will not exceed .$

Output

For each test case output one line containing one integer, indicating the shortest possible time (in minute) BaoBao can move from $to without stopping. If it is impossible for BaoBao to arrive at DreamGrid's house, print "-1" (without quotes) instead.$

Sample Input

Sample Output

Hint

For the first sample test case, BaoBao can follow this path: $.$

For the second sample test case, due to the traffic light rules, BaoBao can't go from $to directly. Instead, he should follow this path: .$

For the third sample test case, it's easy to discover that BaoBao can only go back and forth between $and .$

$题意 n*m的方格每个点都有一个状态状态0 和 1 每秒每个格子都会变成另一个状态现$ $给出起点终点状态为0的点只能上下走状态为1 的点只能左右走问起点到终点的最短路长$

$解析直接bfs搜就好了记录当前点的层次从而判断出现在的状态再将相应的点加入队列。$

$因为 n*m<=1e5 所以外边开vector数组输完n,m之后再开其他数组$

$AC代码$

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 #include <set>
13 #include <utility>
14 #include <stack>
15 using namespace std;
16 const int maxn = 3e5+50,inf = 0x3f3f3f3f, mod = 998244353;
17 const double epx = 1e-6;
18 const double PI = acos(-1.0);
19 typedef long long ll;
20 typedef pair<int,int> pii;
21 const ll INF = 1e18;
22 vector<int> g[maxn];
23 int dir[10][10]= {{1,0},{-1,0},{0,1},{0,-1}};
24 int n,m;
25 int main()
26 {
27     int t;
28     cin>>t;
29     while(t--)
30     {
31         cin>>n>>m;
32         for(int i=0; i<n; i++)
33         {
34             g[i].clear();
35             for(int j=0; j<m; j++)
36             {
37                 int x;
38                 scanf("%d",&x);
39                 g[i].push_back(x);
40             }
41         }
42         int vis[n+10][m+10];
43         int ans[n+10][m+10];
44         memset(vis,0,sizeof(vis));
45         memset(ans,-1,sizeof(ans));
46         int sx,sy,ex,ey;
47         cin>>sx>>sy>>ex>>ey;
48         vis[sx-1][sy-1]=1;
49         ans[sx-1][sy-1]=0;
50         queue<pii> q;
51         q.push(make_pair(sx-1,sy-1));
52         while(!q.empty())
53         {
54             pii temp=q.front();
55             q.pop();
56             int flag;
57             int x=temp.first,y=temp.second;
58             if(ans[x][y]%2==0)
59                 flag=g[x][y];
60             else
61                 flag=!g[x][y];
62             //cout<<ans[x][y]<<" "<<x<<" "<<y<<" "<<flag<<endl;
63             if(flag==0)
64                 for(int i=0; i<2; i++)
65                 {
66                     int x1=x+dir[i][0];
67                     int y1=y+dir[i][1];
68                     if(x1>=0&&x1<n&&y1>=0&&y1<m&&vis[x1][y1]==0)
69                     {
70                         ans[x1][y1]=ans[x][y]+1;
71                         vis[x1][y1]=1;
72                         q.push(make_pair(x1,y1));
73                     }
74                 }
75             else if(flag==1)
76                 for(int i=2; i<4; i++)
77                 {
78                     int x1=x+dir[i][0];
79                     int y1=y+dir[i][1];
80                     if(x1>=0&&x1<n&&y1>=0&&y1<m&&vis[x1][y1]==0)
81                     {
82                         ans[x1][y1]=ans[x][y]+1;
83                         vis[x1][y1]=1;
84                         q.push(make_pair(x1,y1));
85                     }
86                 }
87         }
88         printf("%d
",ans[ex-1][ey-1]);
89     }
90 }

View Code