题干：

n*m矩阵a.若a[i][j]==1则可以往左右走,若a[i][j]==0 则可以往上下走.
每一秒可以按上述规则移动,并且每秒钟矩阵所有的值翻转。
n*m<=1e5.问从(sx,sy)到(tx,ty)的最短时间.

解题报告：

  这题因为不带权值所以不需要考虑Dijkstra，可以根据时间直接判断状态是0还是1。如果状态的变换很复杂的话就考虑分层图就好了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 3e5 + 5;
int n,m;
bool vis[MAX][2];
int nx[4] = {-1,1,0,0};//上，下，左，右
int ny[4] = {0,0,-1,1}; 

int sta[MAX];
struct Node {
	int x,y;
	int pos,t;
	Node(){}
	Node(int x,int y,int pos,int t):x(x),y(y),pos(pos),t(t){}
};
inline int getp(int x,int y) {
	return (x-1) * m + y;
}
int bfs(int a,int b,int c,int d,int st,int ed) {
	queue<Node > q;
	q.push(Node(a,b,st,0));
	vis[st][sta[st]]=1;
	while(!q.empty()) {
		Node cur = q.front();q.pop();
		if(cur.pos == ed) return cur.t;
		int nowsta = (cur.t%2==0) ? sta[cur.pos] : 1-sta[cur.pos];
		if(nowsta == 0) {
			for(int k = 0; k<2; k++) {
				int tx = cur.x + nx[k];
				int ty = cur.y + ny[k];
				if(tx <1 || tx >n || ty < 1 || ty > m) continue;
				if(vis[getp(tx,ty)][nowsta]) continue;
				vis[getp(tx,ty)][nowsta] = 1 ;
				q.push(Node(tx,ty,getp(tx,ty),cur.t+1));
			}
		}
		else {
			for(int k = 2; k<4; k++) {
				int tx = cur.x + nx[k];
				int ty = cur.y + ny[k];
				if(tx <1 || tx >n || ty < 1 || ty > m) continue;
				if(vis[getp(tx,ty)][nowsta]) continue;
				vis[getp(tx,ty)][nowsta] = 1 ;
				q.push(Node(tx,ty,getp(tx,ty),cur.t+1));
			}
			
		}
	}
	return -1;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				vis[(i-1)*m+j][0]=0;
				vis[(i-1)*m+j][1]=0;
			}
		}
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				scanf("%d",&sta[(i-1)*m + j]);
			}
		}
		int stx,sty,edx,edy,st,ed;
		scanf("%d%d",&stx,&sty);
		scanf("%d%d",&edx,&edy);
		st = (stx-1) * m + sty;
		ed = (edx-1) * m + edy;
		int ans = bfs(stx,sty,edx,edy,st,ed);
		printf("%d\n",ans);
	}
	return 0 ;
}