有没有专门做衣服的网站,域名购买 网站建设,怎做网站手机,重庆网站推广效果正题
题目链接:https://jzoj.net/senior/#contest/show/2940/1 题目大意
一个n∗nn*nn∗n的图#xff0c;从000走到111价格为1。kkk个询问#xff0c;询问一个点离边界的最小价格。 解题思路
反向从边界开始跑SPFASPFASPFA即可。 codecodecode
#pragma GCC optimize(从000走到111价格为1。kkk个询问询问一个点离边界的最小价格。 解题思路
反向从边界开始跑SPFASPFASPFA即可。 codecodecode
#pragma GCC optimize(O2)
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int dx[8]{0,0,1,-1,1,-1,1,-1},dy[8]{1,-1,0,0,1,-1,-1,1};
const int N1100;
queueint qx,qy;
int n,m,dis[N][N];
bool v[N][N];
char a[N][N];
void bfs()
{while(!qx.empty()){int xqx.front(),yqy.front();v[x][y]0;qx.pop();qy.pop();for(int k0;k8;k){int zxxdx[k],zyydy[k];if(zx1||zy1||zxn||zyn) continue;int w(a[zx][zy]0)*(a[x][y]1);if(dis[x][y]wdis[zx][zy]){dis[zx][zy]dis[x][y]w;if(!v[zx][zy]){qx.push(zx);qy.push(zy);v[zx][zy]1;}}}}
}
void try_add(int x,int y)
{if(v[x][y]) return;v[x][y]1;dis[x][y]0;qx.push(x),qy.push(y);return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%s,a[i]1);memset(dis,0x3f,sizeof(dis));for(int i1;in;i)try_add(1,i),try_add(i,1),try_add(n,i),try_add(i,n); bfs();for(int i1;im;i){int x,y;scanf(%d%d,x,y);printf(%d ,dis[x][y]);}
}
