#include<bits/stdc++.h>
using namespace std;
int graph[1009][1009];
int visited[1009][1009];
int level[1009][1009];
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int main()
{
while(1)
{
int r,c;
cin>>r>>c;
if(r==0&&c==0)
break;
int row_num;
cin>>row_num;
memset(graph,0,sizeof(graph));
int row,i,j,k;
for(i=0;i<row_num;i++)
{
cin>>row>>k;
for(j=0;j<k;j++)
{
int col;
cin>>col;
graph[row][col]=1;
//cout<<"ROW:"<<row<<" COL:"<<col<<endl;
}
}
memset(visited,0,sizeof(visited));
memset(level,0,sizeof(level));
queue<int>q;
int stx,sty,enx,eny;
cin>>stx>>sty;
cin>>enx>>eny;
visited[stx][sty]=true;
level[stx][sty]=0;
q.push(stx);
q.push(sty);
int ans;
while(!q.empty())
{
int f1,f2;
f1=q.front();
q.pop();
f2=q.front();
q.pop();
for(int in=0;in<4;in++)
{
int v1,v2;
v1=f1+x[in];
v2=f2+y[in];
//cout<<111111111111<<endl;
if(!visited[v1][v2]&&!level[v1][v2])
{
if(v1>=0&&v1<=r&&v2>=0&&v2<=c&&graph[v1][v2]==0)
{
level[v1][v2]=level[f1][f2]+1;
//cout<<"LEVEL:"<<level[v1][v2]<<endl;
q.push(v1);
q.push(v2);
visited[v1][v2]=true;
if(v1==enx&&v2==eny)
ans=level[v1][v2];
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
using namespace std;
int graph[1009][1009];
int visited[1009][1009];
int level[1009][1009];
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int main()
{
while(1)
{
int r,c;
cin>>r>>c;
if(r==0&&c==0)
break;
int row_num;
cin>>row_num;
memset(graph,0,sizeof(graph));
int row,i,j,k;
for(i=0;i<row_num;i++)
{
cin>>row>>k;
for(j=0;j<k;j++)
{
int col;
cin>>col;
graph[row][col]=1;
//cout<<"ROW:"<<row<<" COL:"<<col<<endl;
}
}
memset(visited,0,sizeof(visited));
memset(level,0,sizeof(level));
queue<int>q;
int stx,sty,enx,eny;
cin>>stx>>sty;
cin>>enx>>eny;
visited[stx][sty]=true;
level[stx][sty]=0;
q.push(stx);
q.push(sty);
int ans;
while(!q.empty())
{
int f1,f2;
f1=q.front();
q.pop();
f2=q.front();
q.pop();
for(int in=0;in<4;in++)
{
int v1,v2;
v1=f1+x[in];
v2=f2+y[in];
//cout<<111111111111<<endl;
if(!visited[v1][v2]&&!level[v1][v2])
{
if(v1>=0&&v1<=r&&v2>=0&&v2<=c&&graph[v1][v2]==0)
{
level[v1][v2]=level[f1][f2]+1;
//cout<<"LEVEL:"<<level[v1][v2]<<endl;
q.push(v1);
q.push(v2);
visited[v1][v2]=true;
if(v1==enx&&v2==eny)
ans=level[v1][v2];
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
No comments:
Post a Comment