作者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