SSLOJ 1316.血色先锋军

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 int g[250005][2],h[250005][2];
 7 int map[600][600],n,m;
 8 int flag[600][600];
 9 int fx[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
10 queue<int> q;
11 void bfs()
12 {
13     while (!q.empty())
14     {
15         int x=q.front(); q.pop(); int y=q.front(); q.pop();
16         for (int i=0;i<4;i++)
17         {
18             if (x+fx[i][0]<1||x+fx[i][0]>n||y+fx[i][1]<1||y+fx[i][1]>m||flag[x+fx[i][0]][y+fx[i][1]]==1) continue;
19             map[x+fx[i][0]][y+fx[i][1]]=min(map[x+fx[i][0]][y+fx[i][1]],map[x][y]+1);
20             q.push(x+fx[i][0]); q.push(y+fx[i][1]);
21             flag[x+fx[i][0]][y+fx[i][1]]=1;
22         }
23     }
24 }
25 int main ()
26 {
27     int a,b;
28     cin>>n>>m>>a>>b;
29     memset(map,0x7f,sizeof(map));
30     for (int i=1;i<=a;i++)
31     {
32         scanf("%d%d",&g[i][0],&g[i][1]);
33         flag[g[i][0]][g[i][1]]=1;
34         map[g[i][0]][g[i][1]]=0;
35         q.push(g[i][0]); q.push(g[i][1]);
36     }
37     bfs();
38     for (int i=1,xx,yy;i<=b;i++)
39     {
40         scanf("%d%d",&xx,&yy);
41         printf("%d\n",map[xx][yy]);
42     }
43 }