题目：梅西的过人

messi.pas/c/cpp/

时间限制：1s 空间限制：64M

【题目描述】

梅西来泰州了！这让泰州人民沸腾了，为了体现阿根廷和中国的国际友谊，校长决定让梅西与tzefz队组织一场友谊赛。这场比赛在tzefz大操场进行，把操场分成一个n乘m的矩阵，一开始梅西在(1,1)位置，球门在(n,m)位置，只要梅西能带球到球门处就算梅西胜利。tzefz几乎派出了所有学生来阻挡梅西，但是因为梅西的气场，他们站在场上都不敢动。 如下图，是一个3乘4的球场，每个位置上的数字表示这个位置有没有站tzefz的学生。m是梅西，d是球门。

m 0 1 0

0 0 1 0

1 0 1 d

同时，为了公平起见，限定梅西只能过一个人，就是说梅西能跨入“1”的格子，但只能进入一次。同时规定梅西只能四方向移动，就是说梅西不能从一个格子走到它右上角的格子。 在上面的这个例子中，梅西能通过过一个人来走到球门处。

m 1 0 0

1 1 1 1

0 0 1 d

但在这个例子中，梅西就到不了了，因为他必须过两个人。 在球场上没有时间给你思考！只有一秒钟时间在决定能否到球门处。

【输入数据】

k组数据，给出n，m，分别是矩阵的行数和列数，之后给出n行，每行m个数，每个数是0或者1，表示在这个位置上是否有tzefz的学生。在(1，1)和(n,m)必是0.

【输出数据】

输出k行，给出梅西是否能到达球门，1表示能，0表示不能。

【样例】

messi.in

1

3 4

0 0 1 0

0 0 1 0

1 0 1 0

messi.out

1

【数据规模】 50% 3<=N,M<=100 100% 3<=N,M<=1000, 1<=k<=4

错误代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[105][105][2],ans=0;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
bool a[1005][1005];
struct node
{
    int x,y,step,use;
};
queue<node>q;
int main()
{
	freopen("messi.in","r",stdin);
	freopen("messi.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
    	for(int i=1;i<=n;i++)
        	for(int j=1;j<=m;j++)
            	cin>>a[i][j];
    	q.push((node){1,1,0,0});
    	vis[1][1][0]=1;
    	while(!q.empty())
    	{
        	node tmp=q.front();
        	q.pop();
        	if(tmp.x==n&&tmp.y==m)
        	{
            	cout<<1;
        	    return 0;
        	}
        	for(int i=0;i<4;i++)
        	{
            	int nx=tmp.x+dx[i],ny=tmp.y+dy[i];
            	if(nx<1||ny<1||nx>n||ny>m) continue;
            	if(a[nx][ny]&&tmp.use) continue;
            	if(!a[nx][ny]&&!vis[nx][ny][tmp.use])
            	{
                	vis[nx][ny][tmp.use]=1;
                	q.push((node){nx,ny,tmp.step+1,tmp.use});
            	}
            	if(a[nx][ny]&&!tmp.use&&!vis[nx][ny][1])
            	{
                	vis[nx][ny][1]=1;
                	q.push((node){nx,ny,tmp.step+1,1});
            	}
        	}
    	}
    	puts("0");
	}
    
    return 0;
}