【u026】房间最短路问题

描述

在一个长宽均为10，入口出口分别为（0，5）、（10，5）的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

格式

输入格式

第一排为n(n<=20)，墙的数目。

接下来n排，每排5个实数x，a1，b1，a2，b2。

x表示墙的横坐标（所有墙都是竖直的），a1-b1和a2-b2之间为空缺。

a1、b1、a2、b2保持递增，x1-xn也是递增的。

输出格式

输出最短距离，保留2位小数。

样例1

样例输入1[复制]

2

4 2 7 8 9

7 3 4.5 6 7

样例输出1[复制]

10.06

【题解】

这是一道最短路问题。

这样做。

给每个墙上的两个“裂缝”的端点标号。则每个墙有4个端点(起点和终点除外)。

则第i个墙的第j个端点它的编号为(i - 1) + j;

然后起点的编号为0，终点的编号为4*n + 1;

最后输出0到4*n+1的最短距离；

然后建图的过程如下

枚举第ii个墙和第jj个墙

然后第ii个墙枚举的是第i个端点，第jj个墙枚举的是第j个端点。

设两个端点的坐标为(x1,y1),(x2,y2)；

然后我们就要看看ii+1..jj-1这些墙里面是否有会挡住这两点所构成的直线的墙。

如果有这样的墙，则这两个点不能连线，否则在它们两个点之间建立一条边。

这条边的权值就是两点之间的距离。

可以用两点之间的距离公式求得。

sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))；

然后要判断会不会有墙挡住这条直线则需要用到直线方程的两点式;

已知两个点(x1,y1),(x2,y2)；

则它们所构成的直线方程为

(x-x1)/(x2-x1)=(y-y1)/(y2-y1)

然后两边消一下，换一下。

得到y=(y2-y1)*(x-x1)/(x2-x1) + y1

然后假设我们枚举到ii+1..jj-1中的墙k。

则x=墙k的横坐标

代入之后得到y0;

看看这个y0是不是在k墙的两个窟窿中。如果不是则会撞墙返回false跳过这条边。

如果ii+1..jj-1这些墙都不会阻碍这条直线。则可以在这两个点之间建一条边。

然后还要单独处理起点到其他墙的、其他墙到终点的以及起点到终点的这3种情况。

最后选择用floyd来求最短路即可(简单！)

【代码】

#include <cstdio>

#include <cmath>

#include <cstring>

struct point

{

	double x;

	double height[5];

};

int n, t[200][200] = { 0 };

double w[200][200];

point a[200];

int main()

{

	for (int i = 0; i <= 199; i++)

		for (int j = 0; j <= 199; j++) //这是做floyd算法用的数组。一开始赋值为无穷大。

			w[i][j] = 2100000000 / 3;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) //输入n个墙的信息。

	{

		double x, a1, b1, a2, b2;

		scanf("%lf%lf%lf%lf%lf", &x, &a1, &b1, &a2, &b2);

		a[i].x = x, a[i].height[1] = a1, a[i].height[2] = b1, a[i].height[3] = a2, a[i].height[4] = b2;

	}

	for (int ii = 2; ii <= n; ii++) //第ii列

	{

		for (int i = 1;i <= 4;i++)

			for (int jj = 1; jj <= ii - 1; jj++) //第jj列

			{

				for (int j = 1; j <= 4; j++) //这层要先求出i,j两个点构成的直线方程。

				{

					double  x1, y1, x2, y2;

					x1 = a[ii].x;y1 = a[ii].height[i]; //这是所枚举的两个点的坐标。

					x2 = a[jj].x;y2 = a[jj].height[j];

					bool judge = true;

					for (int kk = jj + 1; kk <= ii - 1; kk++)//它们中间的墙。

					{

						double x = a[kk].x;

						double y0 = ((y2 - y1)*(x - x1) / (x2 - x1)) + y1; //这是这两列的相应的点的直线方程，把第kk列的点的信息代入。

						if ((y0 >= a[kk].height[1] && y0 <= a[kk].height[2]) || (y0 >= a[kk].height[3] && y0 <= a[kk].height[4]))

							judge = true; //如果在两个窟窿里面则是可以添加的边

						else//否则只要有一个不行就判错

						{

							judge = false;

							break;//结束循环了。

						}

					}

					if (judge) //如果可以添加这条边

					{

						int fr = (jj - 1) * 4 + j, to = (ii - 1) * 4 + i;//这是两个点的编号。

						t[fr][0]++; //起点的出度增加。

						t[fr][t[fr][0]] = to;

						w[fr][to] = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));//权值为两点之间的距离。

					}

				}

			}

	}

	//其实下面这两段直接复制上面的同时枚举两个点的片段即可。

	for (int jj = 1; jj <= n; jj++) //这是起点到其他墙的点。(不包括终点)

	{

		for (int j = 1; j <= 4; j++)

		{

			double  x1, y1, x2, y2;

			x1 = 0; y1 = 5; //这下其中的一个点变成是固定的了。

			x2 = a[jj].x; y2 = a[jj].height[j];//现在只需要枚举一个点了。

			bool judge = true;

			for (int kk = 1; kk <= jj- 1; kk++)//然后枚举它们中间的墙，如果它们中间没有墙，则说明一定可以添加，所以初值是true;

			{

				double x = a[kk].x;

				double y0 = ((y2 - y1)*(x - x1) / (x2 - x1)) + y1;//用同样的办法判断是否可以添加这条边。

				if ((y0 >= a[kk].height[1] && y0 <= a[kk].height[2]) || (y0 >= a[kk].height[3] && y0 <= a[kk].height[4]))

					judge = true;

				else

				{

					judge = false;

					break;

				}

			}

			if (judge)

			{

				int fr = 0, to = (jj - 1) * 4 + j;//如果可以就添加这条边。

				t[fr][0]++;

				t[fr][t[fr][0]] = to;

				w[fr][to] = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

			}

		}

	}

	for (int jj = 1; jj <= n; jj++) //其他墙上的点(不包括起点)到终点(4*n+1)

	{

		for (int j = 1; j <= 4; j++)

		{

			double  x1, y1, x2, y2;

			x1 = a[jj].x; y1 = a[jj].height[j];

			x2 = 10; y2 = 5;//这下其中一个固定的点变成了终点

			bool judge = true;

			for (int kk = jj+1; kk <= n; kk++)

			{

				double x = a[kk].x;

				double y0 = ((y2 - y1)*(x - x1) / (x2 - x1)) + y1;

				if ((y0 >= a[kk].height[1] && y0 <= a[kk].height[2]) || (y0 >= a[kk].height[3] && y0 <= a[kk].height[4]))

					judge = true;

				else

				{

					judge = false;

					break;

				}

			}

			if (judge) //如果可以则添加这条边。

			{

				int fr = (jj - 1) * 4 + j, to = 4*n+1;

				t[fr][0]++;

				t[fr][t[fr][0]] = to;

				w[fr][to] = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

			}

		}

	}

   //起点到终点,因为可能可以直接从起点画一条直线就到终点了。所以一定要判断这个。不然会WA！

			double  x1, y1, x2, y2;

			x1 = 0; y1 = 5;

			x2 = 10; y2 = 5; //两个点都是固定的了。

			bool judge = true;

			for (int kk = 1; kk <= n; kk++)//看看起点和终点直接的墙会不会阻碍它们俩画一条直线。

			{

				double x = a[kk].x;

				double y0 = ((y2 - y1)*(x - x1) / (x2 - x1)) + y1;

				if ((y0 >= a[kk].height[1] && y0 <= a[kk].height[2]) || (y0 >= a[kk].height[3] && y0 <= a[kk].height[4]))

					judge = true;

				else

				{

					judge = false;

					break;

				}

			}

			if (judge)//如果不会被阻碍，就画一条边。

			{

				int fr = 0, to = 4 * n + 1;

				t[fr][0]++;

				t[fr][t[fr][0]] = to;

				w[fr][to] = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

			}

	n = 4 * n + 1;//让n变成节点的编号。

	for (int k = 0; k <= n; k++)//从0-n做floyd;

		for (int i = 0; i <= n; i++)

			for (int j = 0; j <= n; j++)

				if (w[i][j] > w[i][k] + w[k][j])

					w[i][j] = w[i][k] + w[k][j];

	printf("%.2lf", w[0][n]); //保留两位小数输出即可。

	return 0;

}

巴特西

【u026】房间最短路问题

描述

在一个长宽均为10，入口出口分别为（0，5）、（10，5）的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

格式

输入格式

第一排为n(n<=20)，墙的数目。

接下来n排，每排5个实数x，a1，b1，a2，b2。

x表示墙的横坐标（所有墙都是竖直的），a1-b1和a2-b2之间为空缺。

a1、b1、a2、b2保持递增，x1-xn也是递增的。

输出格式

输出最短距离，保留2位小数。

样例1

样例输入1[复制]

2
4 2 7 8 9
7 3 4.5 6 7

样例输出1[复制]

10.06

最新文章

热门文章

巴特西

【u026】房间最短路问题

描述

在一个长宽均为10，入口出口分别为（0，5）、（10，5）的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

格式

输入格式

第一排为n(n<=20)，墙的数目。 接下来n排，每排5个实数x，a1，b1，a2，b2。 x表示墙的横坐标（所有墙都是竖直的），a1-b1和a2-b2之间为空缺。 a1、b1、a2、b2保持递增，x1-xn也是递增的。

输出格式

输出最短距离，保留2位小数。

样例1

样例输入1[复制]

2 4 2 7 8 9 7 3 4.5 6 7

样例输出1[复制]

10.06

最新文章

热门文章

第一排为n(n<=20)，墙的数目。

接下来n排，每排5个实数x，a1，b1，a2，b2。

x表示墙的横坐标（所有墙都是竖直的），a1-b1和a2-b2之间为空缺。

a1、b1、a2、b2保持递增，x1-xn也是递增的。

2
4 2 7 8 9
7 3 4.5 6 7