흥미로운 문제로 들립니다. @Xavier Holt의 임무는 매우 중요 할 수 있습니다. "빔은 무기한으로 절대 반사 될 수 없습니다". 방문한 필드 추적 (즉, 특정 필드가 두 번 방문되었는지 여부를 확인하는)을 목표로하는 모든 데이터 구조는 최악의 경우 전체 작업을 상당히 지연시킬 수 있습니다.
여기에 mcdowella가 제안한 그래프 기반 접근 방식을 사용할 수 있습니다. 그러나 빔이 거울 그리드를 통과하는 방식에 대한 규칙이 매우 간단하기 때문에 (위에서 언급 한 것처럼주기 검출 등은 필요하지 않습니다.) 2D 배열을 통해이 작업을 수행 할 수 있습니다. 그러면 현재 상태는 현재 위치 (x, y) 및 현재 방향 (dy, dy)으로 표시되며, 이는 각 미러 유형에 따라 업데이트됩니다.
방금 Java로 구현했습니다. computeResults있어서 입력 5 요소 int[] 어레이 목록
- 결과 [0] = 입력 X-coordiante
- 결과 [1] = 입력 Y-coordiante
- 결과 [2] =를 계산 X 방향
- 결과 [3] = 입력 Y 방향
- 결과 [4] = 미러 필드는 좌측까지 스텝 수
"핵심 로직"은 simulate 메소드에 있습니다.
일부 필드 (특히 필드와 솔루션 경로를 프레임으로 렌더링하는 부분)는 매우 더럽습니다. 그러나 어쨌든 누군가는 재미 있습니다. 어쨌든 아주 오래된 PC에서 2000x2000 격자의 솔루션을 몇 초 만에 계산합니다.
import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class MirrorTracer
{
public static void main(String[] args)
{
//basicTest();
largerTest();
}
private static void basicTest()
{
String input =
"SBB" +
"BBB" +
"SBS";
int sizeX = 3;
int sizeY = 3;
int array[][] = createArray(input, sizeX, sizeY);
// int n = simulate(array, 2, 0, 0, 1);
// System.out.println(n);
List<int[]> results = computeResults(array, sizeX, sizeY);
printResults(array, sizeX, sizeY, results);
}
private static void largerTest()
{
int sizeX = 60;
int sizeY = 60;
int array[][] = createRandomArray(sizeX, sizeY, new Random(0));
List<int[]> results = computeResults(array, sizeX, sizeY);
printResults(array, sizeX, sizeY, results);
showResult(array, sizeX, sizeY, findBestResult(results));
}
private static List<int[]> computeResults(int array[][], int sizeX, int sizeY)
{
List<int[]> results = new ArrayList<int[]>();
for (int x=1; x<sizeX+1; x++)
{
results.add(compute(array, x, 0, 0, 1));
//results.add(compute(array, x, sizeY+1, 0, -1));
}
for (int y=1; y<sizeY+1; y++)
{
results.add(compute(array, 0, y, 1, 0));
//results.add(compute(array, sizeX+1, y, -1, 0));
}
return results;
}
private static int[] compute(int array[][], int x, int y, int dx, int dy)
{
int nx = x + dx;
int ny = y + dy;
int n = simulate(array, x, y, dx, dy);
return new int[]{ nx-1, ny-1, dx, dy, n };
}
private static int simulate(int array[][], int x, int y, int dx, int dy)
{
int steps = 0;
while (true)
{
int nx = x + dx;
int ny = y + dy;
if (isOnBorder(array, nx, ny))
{
break;
}
//System.out.println("Move from "+x+" "+y+" in "+dx+" "+dy+" to "+nx+" "+ny);
int ndx = dy;
int ndy = dx;
if (array[nx][ny] == '/')
{
ndx = -dy;
ndy = -dx;
}
x = nx;
y = ny;
dx = ndx;
dy = ndy;
steps++;
}
return steps;
}
private static boolean isOnBorder(int array[][], int x, int y)
{
return
x == 0 || x == array.length - 1 ||
y == 0 || y == array[x].length - 1;
}
private static int[][] createArray(String input, int sizeX, int sizeY)
{
int array[][] = new int[sizeX+2][sizeY+2];
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
char c = input.charAt((x-1) + (y-1) * sizeX);
array[x][y] = c == 'S' ? '/' : '\\';
}
}
return array;
}
private static int[][] createRandomArray(
int sizeX, int sizeY, Random random)
{
int array[][] = new int[sizeX+2][sizeY+2];
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
boolean b = random.nextBoolean();
array[x][y] = b ? '/' : '\\';
}
}
return array;
}
private static void printResults(
int array[][], int sizeX, int sizeY, List<int[]> results)
{
print(array, sizeX, sizeY);
for (int result[] : results)
{
printResult(result);
}
int bestResult[] = findBestResult(results);
System.out.println("Longest sequence:");
printResult(bestResult);
}
private static void print(int array[][], int sizeX, int sizeY)
{
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
System.out.print((char)array[x][y]);
}
System.out.println();
}
}
private static int[] findBestResult(List<int[]> results)
{
int maxLength = -1;
int maxLengthResult[] = null;
for (int result[] : results)
{
if (result[4] > maxLength)
{
maxLength = result[4];
maxLengthResult = result;
}
}
return maxLengthResult;
}
private static void printResult(int result[])
{
int x = result[0];
int y = result[1];
int dx = result[2];
int dy = result[3];
int n = result[4];
System.out.println("Entering at "+x+" "+y+" in direction "+dx+" "+dy+" does "+n+" steps");
}
private static void showResult(
final int array[][], final int sizeX, final int sizeY,
final int bestResult[])
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI(array, sizeX, sizeY, bestResult);
}
});
}
private static void createAndShowGUI(
final int array[][], final int sizeX, final int sizeY,
final int bestResult[])
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
JPanel resultPanel = new JPanel()
{
protected void paintComponent(Graphics g)
{
super.paintComponent(g);
int cellSizeX = getWidth()/(sizeX+2);
int cellSizeY = getHeight()/(sizeY+2);
g.setColor(Color.BLACK);
for (int y=1; y<sizeY+1; y++)
{
for (int x=1; x<sizeX+1; x++)
{
int x0 = x * cellSizeX;
int y0 = y * cellSizeY;
int x1 = x0 + cellSizeX;
int y1 = y0 + cellSizeY;
if (array[x][y] == '/')
{
g.drawLine(x0+2, y1-2, x1-2, y0+2);
}
else
{
g.drawLine(x0+2, y0+2, x1-2, y1-2);
}
}
}
g.setColor(Color.RED);
int dx = bestResult[2];
int dy = bestResult[3];
int x = bestResult[0]-dx+1;
int y = bestResult[1]-dy+1;
paintSimulation(g, array, x, y, dx, dy, cellSizeX, cellSizeY);
}
private int paintSimulation(
Graphics g, int array[][], int x, int y,
int dx, int dy, int cellSizeX, int cellSizeY)
{
int steps = 0;
while (true)
{
int nx = x + dx;
int ny = y + dy;
int x0 = x * cellSizeX + cellSizeX/2;
int y0 = y * cellSizeY + cellSizeY/2;
int x1 = nx * cellSizeX + cellSizeX/2;
int y1 = ny * cellSizeY + cellSizeY/2;
g.drawLine(x0, y0, x1, y1);
if (isOnBorder(array, nx, ny))
{
break;
}
int ndx = dy;
int ndy = dx;
if (array[nx][ny] == '/')
{
ndx = -dy;
ndy = -dx;
}
x = nx;
y = ny;
dx = ndx;
dy = ndy;
steps++;
}
return steps;
}
};
f.getContentPane().add(resultPanel);
f.setSize(800,800);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
몇 가지 생각 : 1) 광선은 절대 무기한으로 반사 될 수 없습니다. 2) 빔은 시작과는 다른 사각형으로 항상 그리드를 떠납니다. 이것들은 빔이 결코 사상 거울에 부딪치지 않는다는 사실 때문입니다. 따라서 루프를 찾으려는 노력을하지 않아도되고 가능한 입력 빔 중 _ 하프 _에 대해 전체 시뮬레이션을 실행하면됩니다. 즉, 귀하의 알고리즘은 꽤 괜찮은 것 같습니다 - 귀하의 코드가 아니라 전반적인 접근 방식이 아마도 둔화입니다. –
[Memoize?] (http://en.wikipedia.org/wiki/Memoization) –