工信部清理未备案网站,展览展台设计公司,wordpress2级目录伪静态,wordpress可以自动采集吗正题
luogu 7473 题目大意
给出一个正方形区域#xff0c;中间有一些障碍 现在有两个球#xff0c;每次操作可以使两个球同时向一个方向移动#xff0c;直到遇到障碍或边界 现在问你让两个球到同一个位置最少要多少步 解题思路
对于每次操作#xff0c;球只有可能停在障…正题
luogu 7473 题目大意
给出一个正方形区域中间有一些障碍 现在有两个球每次操作可以使两个球同时向一个方向移动直到遇到障碍或边界 现在问你让两个球到同一个位置最少要多少步 解题思路
对于每次操作球只有可能停在障碍四周的格子内边界视为障碍把这些格子记录下来
然后暴力枚举它们之间的连边这里倒着连边从最终状态转移到初始状态
对于每个这样的点x建立状态(x,x)两个值分别为当前状态两个点的位置那么bfs即可
代码
#includecstdio
#includequeue
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 260
using namespace std;
int n, m, q, x, y, w, g, xx, yy, tot, p[N][N], v[N][N], f[N*20][N*20], head[N*20][4], to[N][N][4];
struct rec
{int to, next;
}a[N*20*4];
struct node
{int x, y;
};
queuenoded;
bool check(int x, int y)
{return p[x 1][y] || p[x - 1][y] || p[x][y 1] || p[x][y - 1];
}
void add(int x, int y, int z)
{a[tot].to y;a[tot].next head[x][z];head[x][z] tot;
}
int main()
{scanf(%d%d%d, n, m, q);for (int i 1; i m; i){scanf(%d%d, x, y);p[x][y] 1;}for (int i 1; i n; i)p[i][0] p[i][n 1] p[0][i] p[n 1][i] 1;for (int i 1; i n; i)for (int j 1; j n; j)if (!p[i][j] check(i, j))v[i][j] w;//记下特殊点for (int i 1; i n; i)for (int j 1; j n; j){to[i][j][0] p[i][j - 1] ? v[i][j] : to[i][j - 1][0];//查询往各个方向走会到哪个点to[i][j][1] p[i - 1][j] ? v[i][j] : to[i - 1][j][1];}for (int i n; i 0; --i)for (int j n; j 0; --j){to[i][j][2] p[i][j 1] ? v[i][j] : to[i][j 1][2];to[i][j][3] p[i 1][j] ? v[i][j] : to[i 1][j][3];}for (int i 1; i n; i)for (int j 1; j n; j)if (v[i][j])for (int k 0; k 4; k)add(to[i][j][k], v[i][j], k);//连反边memset(f, 127/3, sizeof(f));for (int i 1; i w; i){d.push((node){i, i});//最终状态f[i][i] 0;}while(!d.empty()){node h d.front();d.pop();for (int k 0; k 4; k)//bfsfor (int i head[h.x][k]; i; i a[i].next)for (int j head[h.y][k]; j; j a[j].next)if (f[a[i].to][a[j].to] 1e8){f[a[i].to][a[j].to] f[h.x][h.y] 1;d.push((node){a[i].to, a[j].to});}}while(q--){scanf(%d%d%d%d, x, y, xx, yy);g x xx y yy ? 0 : 1e8;for (int k 0; k 4; k)g min(g, f[to[x][y][k]][to[xx][yy][k]] 1);//往其中一个方向走然后就可以直接使用bfs得出的结果if (g 1e8) printf(%d\n, g);else puts(-1);}return 0;
}
