Skip to content
A solution for a graph escape problem
Python
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore Add gitignore file Jul 2, 2016
AUTHORS
LICENSE Add license file Jul 2, 2016
README.md Fix typo Sep 22, 2019
description.jpg Fix typo Sep 22, 2019
input.py
input.txt Fix input error Jul 2, 2016
main.py Show found escape paths more elegent Jul 2, 2016

README.md

Problem's description

Problem's description

Problem's assumptions

  1. Every escape path sould have it's unique set of vertices.
  2. If two escape paths have shared vertices, only one of them is accepted as escape path.
  3. If two escape paths have shared vertices, The one which has been seen sooner, will be accepted.
  4. Order of seeing the paths relate to order of seeing the start points.
  5. Order of seeing the start points is the exact order of them in input.txt

Input rules

The input grid graph informations should be placed in input.txt

  • The first line of input.txt is grid's size: n (grid has n 2 nodes)
  • The n next lines are informations about nodes:
    • Every node has 4 directions that can have one of these values:

      • 0: If that direction is not connected.
      • 1: If that direction is connected.
      • 3: If that direction has no more nodes (the node is on border)

      Order of directions are like this: Left-Right-Up-Down

      Example of a node's information: 3130

  • Next lines (to an empty line) are starting points, each line contains a starting point.

There is an example test case in input.txt. You can read it to see how input.txt should be filled.

Prerequisites

  • Python2 (python 2.7 is tested)
You can’t perform that action at this time.