作者RockLee (Now of all times)
看板Prob_Solve
标题Re: [问题] 这次的抠酱资格赛
时间Tue Apr 17 10:32:28 2012
不好意思这部分我可能之前说明的不够清楚,
一开始我也担心过 Leon 大所担心的误差问题,
所以在我的 simulation 中全部都是用 int 在模拟,
没有用到任何的浮点数运算.
方向的表示正如同 LPH66 大所说的,
是用一对整数 (diffX, diffY) 表示前进方向,
例如 (diffX = -3, diffY = -5) 表示每一步以
列数减零点零三, 行数减零点零五的速度前进.
在反射的时侯,
则是以 diffX = -diffX 或 diffY = -diffY 处理.
由於我的 simulation 中全部都是用 int 在模拟,
所以不会有误差问题,
path 会 exactly go back to source.
以下是我将我的 source code 中复杂的 xReflection / yReflection
是否设为 true 的判断先省略後的 pseudo code,
希所可以比较简单的看出来 simulation 的主要想法及不会有误差的问题.
for (int testcase = 1; testcase <= testcases; testcase++)
{
/* 取得输入矩阵, H, W, D 并设定 row, col 为 X 点的列数与行数*/
char[][] real = getCharMatrix(input);
HashSet<Integer> valid = new HashSet<Integer>();
for (int i = row - D; i <= row + D; i++)
{
int range = sqrt((D * D) - ((i - row) * (i - row)));
for (int j = col - range; j <= col + range; j++)
{
int diffX = i - row;
int diffY = j - col;
if (0 == diffX && 0 == diffY) {continue;}
int gcd = gcd(Math.abs(diffX), Math.abs(diffY));
int direction = (((diffX/gcd) + D) << 16) + ((diffY/gcd) + D);
if (valid.contains(direction)) {continue;}
/* 将 x, y 初始化为 X 点中心 */
int x = 100 * row + 50;
int y = 100 * col + 50;
for (int k = 0; k < 100; k++)
{
int nextX = x + diffX;
int nextY = y + diffY;
int xCell = x / 100;
int yCell = y / 100;
int nextXCell = nextX / 100;
int nextYCell = nextY / 100;
boolean xReflection = false;
boolean yReflection = false;
// look one step furthur to decide true next cell for edge
if (0 == nextX % 100) {nextXCell = (nextX + diffX) / 100;}
if (0 == nextY % 100) {nextYCell = (nextY + diffY) / 100;}
/* 根据不同 case 决定是否要将 xReflection 与 yReflection 设为 true */
...
if (xReflection)
{
diffX = -diffX;
if (nextXCell < xCell)
{x = (100 * (nextXCell + 1)) - (x - (100 * (nextXCell + 1)));}
else {x = (100 * nextXCell) + ((100 * nextXCell) - x);}
}
if (yReflection)
{
diffY = -diffY;
if (nextYCell < yCell)
{y = (100 * (nextYCell + 1)) - (y - (100 * (nextYCell + 1)));}
else {y = (100 * nextYCell) + ((100 * nextYCell) - y);}
}
x = x + diffX; y = y + diffY;
if ((100 * row + 50) == x && (100 * col + 50) == y)
{valid.add(direction); break;}
}
}
}
String result = "Case #" + testcase + ": " + valid.size();
output(result);
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.137.132