Analysis: Mirror by Brian Dean


The solution to this problem involves simply simulating the beam of light from every possible starting point, counting the number of bounces until it leaves the grid. There are two possible concerns about this approach, however: is it possible for the beam to continue bouncing forever? And, will this be fast enough to run within the required time limit?

Fortunately, a simple observation helps resovle both of these questions. Each mirror side has two "ports" (say, A and B). If light comes in on A it leaves on B, and if light comes in on B it leaves on A. With a bit of thought, we can therefore see that if light enters the grid at a certain location, there is a unique path it must take until it finally exits -- and if we shine light back in the exit, it will take this same path in reverse. Each mirror side is therefore encountered along exactly two paths, so at worst our method examines every square in the grid only a constant number of times, making the approach run very quickly. We also cannot encounter any cycles, since otherwise the first mirror side we encounter along a cycle would need to have 3 "ports" (two along the cycle, and one along the direction we came from to enter the cycle). If you are familiar with the concept of "graphs" in computer science, this gives a very convenient way to think about the field of mirrors -- as a graph where every node has one or two incident edges.

Here is one simple solution, using lookup tables to deal with the mechanics of deciding how to change direction at each bounce:

#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>

using namespace std;

// direction: 0  1   2   3 
int dr[] =   {1, 0, -1,  0};
int dc[] =   {0, 1,  0, -1};

// new direction after hitting / mirror
int bounce1[] = {3, 2, 1, 0}; 

// new direction after hitting \ mirror 
int bounce2[] = {1, 0, 3, 2}; 

int N, M;
string A[1010];

int trace(int r, int c, int dir) {
  int result = 0;
  while(0 <= r && r < N && 0 <= c && c < M) {
    if(A[r][c] == '/') 
      dir = bounce1[dir];
    else 
      dir = bounce2[dir];
    r += dr[dir];
    c += dc[dir];
    result++;
  }
  return result;
}

int main() {
  freopen("mirror.in", "r", stdin);
  freopen("mirror.out", "w", stdout);

  cin >> N >> M;

  for(int i = 0; i < N; i++) 
    cin >> A[i];

  int best = 0;
  for(int i = 0; i < N; i++) {
    best = max(best, trace(i, 0, 1));
    best = max(best, trace(i, M - 1, 3));
  }
  for(int i = 0; i < M; i++) {
    best = max(best, trace(0, i, 0));
    best = max(best, trace(N - 1, i, 2));
  }
  cout << best << endl;
  
  return 0;
}