PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 這次的摳醬資格賽

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/04/17 10:32)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串5/5 (看更多)

不好意思這部分我可能之前說明的不夠清楚, 一開始我也擔心過 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