阿里云网站建设 部署与发布,汇通网做期货的网站做期货的网站,user post wordpress,asp.net4.5网站开发问题描述 这天, 小明在玩迷宫游戏。 迷宫为一个 nn 的网格图, 小明可以在格子中移动, 左上角为 (1,1), 右下角 (n, n)为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。 假如小明处在格子(x1,y1), 同时有… 问题描述 这天, 小明在玩迷宫游戏。 迷宫为一个 n×n 的网格图, 小明可以在格子中移动, 左上角为 (1,1), 右下角 (n, n)为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。 假如小明处在格子(x1,y1), 同时有一个传送门连接了格子(x1,y1) 和 (x2,y2), 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能越过边界), 也可以花费 1 的步数通过传送门走到格子 (x2,y2) 去。 而对于同一个迷宫, 小明每次进入的初始格子是在这n×n 个格子中均匀随 机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短 步数的期望值是多少。 输入格式 输入共 1m 行, 第一行为两个正整数 n,m 。 后面 mm 行, 每行四个正整数 xi1,yi1,xi2,yi2 表示第 i 个传送门连接的两个格子坐标。 输出格式 输出共一行, 一个浮点数表示答案 (请保留两位小数)。 样例输入 2 1
1 1 2 2 样例输出 0.75反向搜索 只要搜一次就行
另外本题不标记 因为传送门会使之前的结果不一定是最优的。增加了空间复杂度。
#includebits/stdc.h
using namespace std;
#define int long long
#define fp(i,a,b) for(int ia;ib;i)
#define PII pairint,int
const int N2e310;
const int mod1e97;
const double eps1e-5;
typedef double db;
int dx[]{0,0,1,-1};
int dy[]{1,-1,0,0};
int n,m;
int dist[N][N];
vectorPIIdoor[N][N];
bool is_door[N][N];
void bfs()
{ memset(dist,0x3f,sizeof dist);dist[n][n]0;queuePIIq;q.push({n,n});while(q.size()){auto tq.front();q.pop();for(int p0;p4;p){int Xdx[p]t.first,Ydy[p]t.second;if(X1||Xn||Y1||Yn) continue;if(dist[X][Y]dist[t.first][t.second]1){dist[X][Y]dist[t.first][t.second]1;q.push({X,Y});}if(is_door[t.first][t.second])//如果当前点可以使用传送门 {//因为是反向搜图可以多对一for(auto s:door[t.first][t.second]){//取出里面的点if(dist[s.first][s.second]dist[t.first][t.second]1){dist[s.first][s.second]dist[t.first][t.second]1;q.push({s.first,s.second});} } }}}
}
signed main()
{cinnm;for(int i1;im;i){int a,b,c,d;cinabcd;door[a][b].push_back({c,d});door[c][d].push_back({a,b});is_door[a][b]is_door[c][d]true;}bfs();int sum0;for(int i1;in;i){for(int j1;jn;j){sumdist[i][j]; }}coutfixedsetprecision(2)1.0*sum/(n*n)\n;return 0;
}
