title: Shortest meeting point of two paths
body: <p><a href="https://i.stack.imgur.com/to4Hp.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/to4Hp.png" alt="Example image"></a></p>
  
  <h2>Explanation :</h2>
  
  <p>In the example picture above there is a green circle following an arbitrary path.   </p>
  
  <p>I want the red circle to meet the green circle in the minimum steps possible as demonstrated in the picture. </p>
  
  <p>The circles can move to any of the 8 adjacent cells in one step and black cells can’t be traversed. </p>
  
  <p>The paths are represented as a list of coordinates. In this case, <strong>the green path
  is [(0,3),(0,2),(0,1)...(5,0)]</strong>.</p>
  
  <p>To find the shortest meeting point I can iterate though each coordinate in the green path list and use the A* algorithm to find the shortest path from the red circle to that coordinate. If the length of the path returned is equal to the number of steps it takes the green circle to get to that coordinate, then the shortest meeting point path is found.</p>
  
  <p>This is of course, a brute force approach and the java code looks something like this:</p>
  
  <pre><code>List&lt;Coord&gt; minMeetingPointPath(Coord redLoc, List&lt;Coord&gt; greenPath) {
      for (int step = 0; step &lt; greenPath.size(); step++) {
          Coord greenLoc = greenPath.get(step);
          List&lt;Coord&gt; redPath = shortestPathAStar(redLoc, greenLoc);
          if (redPath.size() == step)
              return redPath;
      }
      return null;
  }
  </code></pre>
  
  <h2>Question</h2>
  
  <p>So my question is: </p>
  
  <ol>
  <li>Is there a <strong>more efficient way</strong> to solve this problem without using a brute force approach?</li>
  </ol>