题目链接：The 18th Zhejiang University Programming Contest Sponsored by TuSimple - G Traffic Light
题解：
题意自己翻译，此题首先肯定是要广搜的，不过要开一个1e5*1e5的数组好像有点困难，
所以用结构体来存每个点的下标，然后从源点开始广搜。定义一个pair<node,int>，第一个存节点信息，第二个存到当前节点的步数，因为还要处理到达每个节点的状态。
状态：走奇数步并且状态为1与走偶数步状态为0的结果是一样的，都是向左或向右移动。走偶数步并且状态为1与走奇数步状态为0的结果也是一样，可以向上或向下移动。
最后定义一个pair的队列。
代码：
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <utility>
#define IO ios::sync_with_stdio(0);\
cin.tie();cout.tie();
using namespace std;
;
struct node
{
int i,j,value;
int flag;
} res[N];
pair <node,int> p;
queue <pair<node,int > > q;
int main()
{
int T;
cin >> T;
while(T--)
{
memset(res,,sizeof(res));
;
cin >> n >> m;
; i <= n; i++)
; j <= m; j++)
cin >> x,res[++num].value = x,res[num].i = i,res[num].j=j;
int x1,y1,x2,y2;
cin >>x1>>y1>>x2>>y2;
;
res[(x1-)*m + y1].flag = ;
p.first = res[(x1-)*m + y1];
p.second = sum;
q.push(p);
,ff = ;
while(!q.empty())
{
pair <node,int> pp;
pp = q.front();
q.pop();
int i = pp.first.i,j = pp.first.j,value = pp.first.value,sum = pp.second;
if(i==x2&&j==y2)
{
ans = sum;
ff = ;
break;
}
)&&value==)||(!(sum&)&&value==))
{
<=n&&res[i*m+j].flag==)
{
pp.first.i = i+,pp.first.j = j,pp.first.value = res[(i)*m+j].value;
pp.first.flag = ;
res[(i)*m+j].flag = ;
pp.second = sum+;
q.push(pp);
}
>&&res[(i-)*m+j].flag==)
{
pp.first.i = i-,pp.first.j = j,pp.first.value = res[(i-)*m+j].value;
pp.first.flag = ;
res[(i-)*m+j].flag = ;
pp.second = sum+;
q.push(pp);
}
}
else
{
<=m&&res[(i-)*m+j+].flag==)
{
pp.first.i = i,pp.first.j = j+,pp.first.value = res[(i-)*m+j+].value;
pp.first.flag = ;
res[(i-)*m+j+].flag = ;
pp.second = sum+;
q.push(pp);
}
>&&res[(i-)*m+j-].flag==)
{
pp.first.i = i,pp.first.j = j-,pp.first.value = res[(i-)*m+j-].value;
pp.first.flag = ;
res[(i-)*m+j-].flag = ;
pp.second = sum+;
q.push(pp);
}
}
}
printf();
while(!q.empty())q.pop();
}
;
}
/*
4
2 3
1 1 0
0 1 0
1 3 2 1
2 3
1 0 0
1 1 0
1 3 1 2
2 2
1 0
1 0
1 1 2 2
1 2
0 1
1 1 1 1
*/