#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int mat[1001][1001];
int color[1001][1001];
int cost[1001][1001];
int X[4]= {1,0,-1,0};
int Y[4]= {0,1,0,-1};
int main()
{
int a,b,R,C,Nr,x,y,r,c,Nb,m,n;
while(scanf("%d%d",&R,&C)&&R&&C)
{
memset(mat,0,sizeof(mat));
memset(color,0,sizeof(color));
memset(cost,0,sizeof(cost));
scanf("%d",&Nr);
for(x=1; x<=Nr; x++)
{
scanf("%d%d",&r,&Nb);
//r=row number,Nb=number of bombs
for(y=1; y<=Nb; y++)
{
scanf("%d",&c);
mat[r][c]=-1;
}
}
scanf("%d%d",&a,&b);
int ua,ub,va,vb,k;
queue<int>Q;
Q.push(a);
Q.push(b);
color[a][b] = 1;
while(!Q.empty())
{
ua = Q.front();
Q.pop();
ub = Q.front();
Q.pop();
for(k=0; k<4; k++)
{
va = ua+X[k];
vb = ub+Y[k];
if((va>=0&&va<R) && (vb>=0&&vb<C)&& mat[va][vb]==0)
{
if(color[va][vb]==0)
{
color[va][vb]=1;
Q.push(va);
Q.push(vb);
cost[va][vb]=cost[ua][ub]+1;
}
}
}
}
scanf("%d%d",&m,&n);
printf("%d\n",cost[m][n]);
}
return 0;
}
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int mat[1001][1001];
int color[1001][1001];
int cost[1001][1001];
int X[4]= {1,0,-1,0};
int Y[4]= {0,1,0,-1};
int main()
{
int a,b,R,C,Nr,x,y,r,c,Nb,m,n;
while(scanf("%d%d",&R,&C)&&R&&C)
{
memset(mat,0,sizeof(mat));
memset(color,0,sizeof(color));
memset(cost,0,sizeof(cost));
scanf("%d",&Nr);
for(x=1; x<=Nr; x++)
{
scanf("%d%d",&r,&Nb);
//r=row number,Nb=number of bombs
for(y=1; y<=Nb; y++)
{
scanf("%d",&c);
mat[r][c]=-1;
}
}
scanf("%d%d",&a,&b);
int ua,ub,va,vb,k;
queue<int>Q;
Q.push(a);
Q.push(b);
color[a][b] = 1;
while(!Q.empty())
{
ua = Q.front();
Q.pop();
ub = Q.front();
Q.pop();
for(k=0; k<4; k++)
{
va = ua+X[k];
vb = ub+Y[k];
if((va>=0&&va<R) && (vb>=0&&vb<C)&& mat[va][vb]==0)
{
if(color[va][vb]==0)
{
color[va][vb]=1;
Q.push(va);
Q.push(vb);
cost[va][vb]=cost[ua][ub]+1;
}
}
}
}
scanf("%d%d",&m,&n);
printf("%d\n",cost[m][n]);
}
return 0;
}
0 comments: (+add yours?)
Post a Comment