【高斯消元 求期望】ZJUT 1423 地下迷宫 + ZJUT 1317 掷飞盘

KIDx的解题报告

1、地下迷宫
Description

由于山体滑坡，DK被困在了地下蜘蛛王国迷宫。为了抢在DH之前来到TFT，DK必须尽快走出此迷宫。此迷宫仅有一个出口，而由于大BOSS的力量减弱影响到了DK，使DK的记忆力严重下降，他甚至无法记得他上一步做了什么。所以他只能每次等概率随机的选取一个方向走。当然他不会选取周围有障碍的地方走。如DK周围只有两处空地，则每个都有1/2的概率。现在要求他平均要走多少步可以走出此迷宫。
Input

先是一行两个整数N, M(1<=N, M<=10)表示迷宫为N*M大小，然后是N行，每行M个字符，'.'表示是空地，'E’表示出口，'D’表示DK，'X’表示障碍。
Output

如果DK无法走出或要超过1000000步才能走出，输出tragedy!，否则输出一个实数表示平均情况下DK要走几步可以走出迷宫，四舍五入到小数点后两位。

Sample Input

1 2
ED
3 3
D.X
.X.
X.E
Sample Output:

1.00
tragedy!

 

解析：E[i]表示从i点到达终点的期望步数

设i的临近可达点有a1, a2, a3,...,an

E[i]可以随机选一个临近点再走到终点

则平均步数E[i] = ((E[a1]+1) + (E[a2]+1) + ... + (E[an]+1)) / n;

化简得n*E[i] - E[a1] - E[a2] - ... - E[an] = n

设s为起点，e为终点：

显然对于e点有方程：E[e] = 0

然后对每个点都建立一个方程然后高斯消元求出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\n", x[1]);
		else puts ("tragedy!");
	}
	return 0;
}

 

2、掷飞盘
Description

m个人位于正m边形的顶点上，彼此抛掷飞盘。他们共有两个飞盘，且开始时这两个飞盘位于相距为n的两个人的手中（相邻两个人相距为1，依此类推）。在每次抛掷时两个飞盘被同时抛出，飞盘都以1/2的概率被抛到掷飞盘的人左边相邻的人，1/2的概率被抛到右边相邻的人。此过程一直进行，直到两个飞盘被掷到同一个人手中，求此抛掷飞盘的游戏平均情况下(期望)会在抛掷几次后结束。
Input

每行有两个整数m (2<m<=100)，n (0 < n < m)。
Output

对每组数据m,n，输出平均所需步数(四舍五入，保留两位小数），如果有限步内不可能结束就输出INF。
Sample Input

3 1
4 1
Sample Output

4.00
INF

 

解析：设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\n", x[has[n]]);		//输出E[n]
	}
    return 0;
}