【ガウス消元期待】ZJUT 1423地下迷宮+ZJUT 1317投飛盤
KIDxの解題報告
1、地下迷宮Description
山崩れのため、DKは地下クモ王国の迷宮に閉じ込められた.DHの前にTFTに来るためには、DKはできるだけ早くこの迷路を出なければならない.この迷路には出口が一つしかないが、大ボスの力が弱まってDKに影響を及ぼし、DKの記憶力が著しく低下し、前に何をしたかさえ覚えていない.だから彼は毎回確率を待ってランダムに1つの方向を選ぶしかありません.もちろん彼は周囲の障害のある場所を選ばない.DK周辺に空き地が2箇所しかない場合,それぞれ1/2の確率がある.今、彼に平均何歩歩いてこの迷路を出ることができるかを要求している.Input
まず1行の2つの整数N、M(1<=N、M<=10)は迷路がN*Mの大きさであることを表し、それからN行で、各行のM文字、'.'空き地を表し、「E」は出口を表し、「D」はDKを表し、「X」は障害を表す.Output
DKが出られないか1000000ステップを超えなければ出られない場合はtragedyを出力します!,そうでなければ実数を出力して平均を表す場合、DKは数歩歩いて迷路を出ることができ、小数点以下の2桁まで四捨五入することができます.
Sample Input
1 2ED3 3D.X.X.X.ESample Output:
1.00tragedy!
解析:E[i]はi点から終点までの所望の歩数を表す
iの近接到達点はa 1,a 2,a 3,...,an
E[i]ランダムに1つの近接点を選んでゴールまで歩くことができる
平均ステップ数E[i]=((E[a 1]+1)+(E[a 2]+1)+...+(E[an]+1))/n;
簡略化n*E[i]-E[a 1]-E[a 2]-...-E[an] = n
sを起点とし、eを終点とする.
明らかにe点に対して方程式がある:E[e]=0
それから各点に対してすべて1つの方程式を創立してそれからガウス消元はE[s]を求めることができます
2、フライングディスクDescription
m個人は正m辺形の頂点に位置し、互いに飛盤を投げ合う.彼らは2つのディスクを共有し、最初はnから離れた2人の手に位置していた(隣接する2人は1から1まで離れていた).投げるたびに2つのディスクが同時に投げ出され、ディスクが1/2の確率でディスクを投げた人の左側に隣接する人、1/2の確率で右隣に投げられた人.このプロセスは、2つのディスクが同じ人の手に投げ込まれるまで行われ、このディスクを投げるゲームの平均を求める場合(所望)は数回投げた後に終了する.Input
各行には2つの整数m(2各データm,nのセットに対して、平均必要ステップ数(四捨五入、小数2桁保持)を出力し、有限ステップ内で終了不可能であればINFを出力する.Sample Input
3 14 1Sample Output
4.00INF
解析:E[n]をnから0までの距離の所望のステップ数とすると、明らかにE[0]=0
距離がnになる組み合わせは,左左(距離が不変),右右(距離が不変),左右(n−2から拡大),右左(n+2から縮小)である.
そこでE[n]に対して:
E[n] = [(E[n]+1) + (E[n]+1) + (E[n-2]+1) + (E[n+2]+1)]/4
簡略化:2*E[n]-E[n-2]-E[n+2]=4
1、地下迷宮Description
山崩れのため、DKは地下クモ王国の迷宮に閉じ込められた.DHの前にTFTに来るためには、DKはできるだけ早くこの迷路を出なければならない.この迷路には出口が一つしかないが、大ボスの力が弱まってDKに影響を及ぼし、DKの記憶力が著しく低下し、前に何をしたかさえ覚えていない.だから彼は毎回確率を待ってランダムに1つの方向を選ぶしかありません.もちろん彼は周囲の障害のある場所を選ばない.DK周辺に空き地が2箇所しかない場合,それぞれ1/2の確率がある.今、彼に平均何歩歩いてこの迷路を出ることができるかを要求している.Input
まず1行の2つの整数N、M(1<=N、M<=10)は迷路がN*Mの大きさであることを表し、それからN行で、各行のM文字、'.'空き地を表し、「E」は出口を表し、「D」はDKを表し、「X」は障害を表す.Output
DKが出られないか1000000ステップを超えなければ出られない場合はtragedyを出力します!,そうでなければ実数を出力して平均を表す場合、DKは数歩歩いて迷路を出ることができ、小数点以下の2桁まで四捨五入することができます.
Sample Input
1 2ED3 3D.X.X.X.ESample Output:
1.00tragedy!
解析:E[i]はi点から終点までの所望の歩数を表す
iの近接到達点はa 1,a 2,a 3,...,an
E[i]ランダムに1つの近接点を選んでゴールまで歩くことができる
平均ステップ数E[i]=((E[a 1]+1)+(E[a 2]+1)+...+(E[an]+1))/n;
簡略化n*E[i]-E[a 1]-E[a 2]-...-E[an] = n
sを起点とし、eを終点とする.
明らかにe点に対して方程式がある:E[e]=0
それから各点に対してすべて1つの方程式を創立してそれからガウス消元はE[s]を求めることができます
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define M 101
#define eps 1e-9
int equ, var;
double a[M][M], x[M];
int r, c, has[15][15], sx, sy, ex, ey;
char map[15][15];
bool vis[15][15];
int xm[] = {-1, 0, 1, 0};
int ym[] = {0, 1, 0, -1};
int Gauss ()
{
int i, j, k, col, max_r;
for (k = 0, col = 0; k < equ && col < var; k++, col++)
{
max_r = k;
for (i = k+1; i < equ; i++)
if (fabs (a[i][col]) > fabs (a[max_r][col]))
max_r = i;
if (fabs (a[max_r][col]) < eps) return 0; //
if (k != max_r)
{
for (j = col; j < var; j++)
swap (a[k][j], a[max_r][j]);
swap (x[k], x[max_r]);
}
x[k] /= a[k][col];
for (j = col+1; j < var; j++) a[k][j] /= a[k][col];
a[k][col] = 1;
for (i = 0; i < equ; i++) if (i != k)
{
x[i] -= x[k] * a[i][k];
for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col];
a[i][col] = 0;
}
}
return 1;
}
struct point{
int x, y;
};
void bfs ()
{
int u, v, i, n, en = 1;
memset (vis, false, sizeof(vis));
memset (has, -1, sizeof(has));
point ft, tp;
ft.x = sx, ft.y = sy;
queue<point> q;
q.push (ft);
// E(e) = 0
has[ex][ey] = 0; // 0
a[0][0] = 1, x[0] = 0;
has[sx][sy] = en++; // 1
//bfs
while (!q.empty())
{
ft = q.front();
q.pop();
if (map[ft.x][ft.y] == 'E') continue; // e
u = has[ft.x][ft.y];
n = 0;
//n*E(u) - E(a1) - E(a2) -... = n
for (i = 0; i < 4; i++)
{
tp.x = ft.x + xm[i];
tp.y = ft.y + ym[i];
if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c) continue;
if (map[tp.x][tp.y] == 'X') continue;
// ， u v
if (has[tp.x][tp.y] > -1)
v = has[tp.x][tp.y];
else v = has[tp.x][tp.y] = en++;
++n;
a[u][v] = -1;
//
if (vis[tp.x][tp.y]) continue;
vis[tp.x][tp.y] = true;
q.push (tp);
}
//u
a[u][u] = x[u] = n;
}
equ = var = en;
}
int main()
{
int i, j;
while (~scanf ("%d%d", &r, &c))
{
for (i = 0; i < r; i++) scanf ("%s", map[i]);
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
if (map[i][j] == 'D') sx = i, sy = j;
else if (map[i][j] == 'E') ex = i, ey = j;
}
}
//
for (i = 0; i < M; i++) for (j = 0; j < M; j++) a[i][j] = 0;
bfs ();
if (Gauss()) printf ("%.2f
", x[1]);
else puts ("tragedy!");
}
return 0;
}2、フライングディスクDescription
m個人は正m辺形の頂点に位置し、互いに飛盤を投げ合う.彼らは2つのディスクを共有し、最初はnから離れた2人の手に位置していた(隣接する2人は1から1まで離れていた).投げるたびに2つのディスクが同時に投げ出され、ディスクが1/2の確率でディスクを投げた人の左側に隣接する人、1/2の確率で右隣に投げられた人.このプロセスは、2つのディスクが同じ人の手に投げ込まれるまで行われ、このディスクを投げるゲームの平均を求める場合(所望)は数回投げた後に終了する.Input
各行には2つの整数m(2
3 14 1Sample Output
4.00INF
解析:E[n]をnから0までの距離の所望のステップ数とすると、明らかにE[0]=0
距離がnになる組み合わせは,左左(距離が不変),右右(距離が不変),左右(n−2から拡大),右左(n+2から縮小)である.
そこでE[n]に対して:
E[n] = [(E[n]+1) + (E[n]+1) + (E[n-2]+1) + (E[n+2]+1)]/4
簡略化:2*E[n]-E[n-2]-E[n+2]=4
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define M 105
#define eps 1e-9
int equ, var;
double a[M][M], x[M];
int Gauss ()
{
int i, j, k, col, max_r;
for (k = 0, col = 0; k < equ && col < var; k++, col++)
{
max_r = k;
for (i = k+1; i < equ; i++)
if (fabs (a[i][col]) > fabs (a[max_r][col]))
max_r = i;
if (fabs (a[max_r][col]) < eps) return 0;
if (k != max_r)
{
for (j = col; j < var; j++)
swap (a[k][j], a[max_r][j]);
swap (x[k], x[max_r]);
}
x[k] /= a[k][col];
for (j = col+1; j < var; j++) a[k][j] /= a[k][col];
a[k][col] = 1;
for (i = 0; i < equ; i++) if (i != k)
{
x[i] -= x[k] * a[i][k];
for (j = col+1; j < var; j++) a[i][j] -= a[k][j] * a[i][col];
a[i][col] = 0;
}
}
return 1;
}
int has[M], k, f, m; //has[i] i ，f=m/2
int cal (int n) // n， n 0， m
{
if (n < 0) n = -n;
if (n > f) n = m - n;
return n;
}
void dfs (int n)
{
n = cal (n);
if (has[n] >= 0) return ;
has[n] = k++;
dfs (n-2);
dfs (n+2);
}
int main ()
{
int n, i, j;
while (~scanf ("%d%d", &m, &n))
{
f = m >> 1;
n = cal (n); // n，trick
memset (has, -1, sizeof(has));
k = 0;
dfs (n); //dfs ，
if (has[0] == -1)
{
puts ("INF");
continue;
}
//
equ = var = k;
for (i = 0; i < k; i++)
for (j = 0; j < k; j++)
a[i][j] = 0;
//
a[has[0]][has[0]] = 1; x[has[0]] = 0; //E[0] = 0
for (i = 1; i <= f; i++)
{
//2*E[n] - E[n-2] - E[n+2] = 4
if (has[i] == -1) continue; //i
int u = has[i], v;
a[u][u] = 2; //E[n]
v = has[cal(i+2)]; //E[n+2]
--a[u][v];
v = has[cal(i-2)]; //E[n-2]
--a[u][v];
x[u] = 4; //
}
Gauss ();
printf ("%.2f
", x[has[n]]); // E[n]
}
return 0;
}