#include<bits/stdc++.h>
using namespace std;
long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
char s[1010][1010];
long dis[1010][1010]={0},vis[1010][1010]={0};
long bfs(long x,long y)
{
queue< pair<long,long> >q;
pair<long,long>pr;
long x1,y1,i1;
dis[x][y]=0;
vis[x][y]=1;
q.push(make_pair(x,y));
while(!q.empty())
{
pr=q.front();
x1=pr.first;
y1=pr.second;
for(i1=0;i1<4;i1++)
{
x1=pr.first+dx[i1];
y1=pr.second+dy[i1];
if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='#'))
{
dis[x1][y1]=dis[pr.first][pr.second]+1;
q.push(make_pair(x1,y1));
vis[x1][y1]=1;
if(s[x1][y1]=='h')
{
return dis[x1][y1];
}
}
}
q.pop();
}
}
int main()
{
while(cin>>row>>col)
{
if(row==0&&col==0)
break;
long n,i,j,rnumbr,pos,a;
cin>>n;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
s[i][j]='*';
dis[i][j]=0;
vis[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
cin>>rnumbr;
cin>>a;
for(j=1;j<=a;j++)
{
cin>>pos;
s[rnumbr][pos]='#';
}
}
long sx,sy,ddx,ddy;
cin>>sx>>sy>>ddx>>ddy;
s[ddx][ddy]='h';
cout<<bfs(sx,sy)<<endl;
}
return 0;
}
using namespace std;
long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
char s[1010][1010];
long dis[1010][1010]={0},vis[1010][1010]={0};
long bfs(long x,long y)
{
queue< pair<long,long> >q;
pair<long,long>pr;
long x1,y1,i1;
dis[x][y]=0;
vis[x][y]=1;
q.push(make_pair(x,y));
while(!q.empty())
{
pr=q.front();
x1=pr.first;
y1=pr.second;
for(i1=0;i1<4;i1++)
{
x1=pr.first+dx[i1];
y1=pr.second+dy[i1];
if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='#'))
{
dis[x1][y1]=dis[pr.first][pr.second]+1;
q.push(make_pair(x1,y1));
vis[x1][y1]=1;
if(s[x1][y1]=='h')
{
return dis[x1][y1];
}
}
}
q.pop();
}
}
int main()
{
while(cin>>row>>col)
{
if(row==0&&col==0)
break;
long n,i,j,rnumbr,pos,a;
cin>>n;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
s[i][j]='*';
dis[i][j]=0;
vis[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
cin>>rnumbr;
cin>>a;
for(j=1;j<=a;j++)
{
cin>>pos;
s[rnumbr][pos]='#';
}
}
long sx,sy,ddx,ddy;
cin>>sx>>sy>>ddx>>ddy;
s[ddx][ddy]='h';
cout<<bfs(sx,sy)<<endl;
}
return 0;
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন