Untitled

 avatar
unknown
plain_text
2 years ago
1.3 kB
2
Indexable
#include<iostream>
using namespace std;
int q_x[100000];
int q_y[100000];
int bot=-1;
int top=-1;
void push(int i,int j)
{
	bot++;
	q_x[bot]=i;
	q_y[bot]=j;
}
void pop(){top++;}
bool is_emty(){return top==bot;}
//-----------------------------------
int n,m;
char a[300][300];
int vis[300][300];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int x_start,y_start,x_end,y_end;


void BFS()
{
	top=bot=-1;
	push(x_start,y_start);
	vis[x_start][y_start]=-1;
	while(!is_emty())
	{
		int f1 = q_x[top+1];
		int f2 = q_y[top+1];
		pop();
		for(int k=0;k<4;k++)
		{
			int i1 =f1;
			int j1 = f2;
			while (true)
			{
				i1 += dx[k];
				j1 += dy[k];
				if(a[i1][j1]=='1' || i1<1 ||i1>n ||j1<1||j1>m)
					break;
				if(vis[i1][j1]==-1)
				{
					vis[i1][j1]=vis[f1][f2]+1;
					push(i1,j1);
				}
				else if(vis[i1][j1]>vis[f1][f2]+1)
				{
					vis[i1][j1]=vis[f1][f2]+1;
					push(i1,j1);
				}

			}
		}
	}
}
int main()
{
	int T;
	cin>>T;
	for(int tc=1;tc<=T;tc++)
	{
		cin>>m>>n;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				vis[i][j]=-1;
			}
		}
		cin>>y_start>>x_start>>y_end>>x_end;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
			}
		}
		BFS();
		cout<<vis[x_end][y_end]<<endl;
	}
	return 0;
}
Editor is loading...