問題描述

這天, 小明在玩迷宮游戲。

迷宮為一個(gè) n×n?的網(wǎng)格圖, 小明可以在格子中移動(dòng), 左上角為 (1,1), 右下角?(n, n)為終點(diǎn)。迷宮中除了可以向上下左右四個(gè)方向移動(dòng)一格以外, 還有?m?個(gè)雙向傳送門可以使用, 傳送門可以連接兩個(gè)任意格子。

假如小明處在格子(x1?,y1?), 同時(shí)有一個(gè)傳送門連接了格子(x1?,y1?)?和 (x2?,y2?), 那么小明既可以花費(fèi) 1 的步數(shù)向上下左右四個(gè)方向之一走一格 (不能越過邊界), 也可以花費(fèi) 1 的步數(shù)通過傳送門走到格子 (x2?,y2?)?去。

而對(duì)于同一個(gè)迷宮, 小明每次進(jìn)入的初始格子是在這n×n?個(gè)格子中均勻隨 機(jī)的 (當(dāng)然運(yùn)氣好可以直接隨機(jī)到終點(diǎn)), 他想知道從初始格子走到終點(diǎn)的最短 步數(shù)的期望值是多少。

輸入格式

輸入共 1+m?行, 第一行為兩個(gè)正整數(shù) n,m?。

后面?mm?行, 每行四個(gè)正整數(shù) xi1?,yi1?,xi2?,yi2??表示第?i?個(gè)傳送門連接的兩個(gè)格子坐標(biāo)。

輸出格式

輸出共一行, 一個(gè)浮點(diǎn)數(shù)表示答案 (請(qǐng)保留兩位小數(shù))。

樣例輸入

2 1
1 1 2 2 

樣例輸出

0.75

反向搜索? 只要搜一次就行

另外本題不標(biāo)記 因?yàn)閭魉烷T會(huì)使之前的結(jié)果不一定是最優(yōu)的。增加了空間復(fù)雜度。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e3+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,m;
int dist[N][N];
vector<PII>door[N][N];
bool is_door[N][N];
void bfs()
{    memset(dist,0x3f,sizeof dist);dist[n][n]=0;queue<PII>q;q.push({n,n});while(q.size()){auto t=q.front();q.pop();for(int p=0;p<4;p++){int X=dx[p]+t.first,Y=dy[p]+t.second;if(X<1||X>n||Y<1||Y>n) 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])//如果當(dāng)前點(diǎn)可以使用傳送門 {//因?yàn)槭欠聪蛩褕D，可以多對(duì)一for(auto s:door[t.first][t.second]){//取出里面的點(diǎn)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()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c,d;cin>>a>>b>>c>>d;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 sum=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){sum+=dist[i][j];	}}cout<<fixed<<setprecision(2)<<1.0*sum/(n*n)<<"\n";return 0;
}