{"action":"opened","issue":{"url":"https://api.github.com/repos/qss512985866/MMMMMaze/issues/1","repository_url":"https://api.github.com/repos/qss512985866/MMMMMaze","labels_url":"https://api.github.com/repos/qss512985866/MMMMMaze/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/qss512985866/MMMMMaze/issues/1/comments","events_url":"https://api.github.com/repos/qss512985866/MMMMMaze/issues/1/events","html_url":"https://github.com/qss512985866/MMMMMaze/issues/1","id":186164764,"number":1,"title":"Maze.java","user":{"login":"qss512985866","id":8226937,"avatar_url":"https://avatars.githubusercontent.com/u/8226937?v=3","gravatar_id":"","url":"https://api.github.com/users/qss512985866","html_url":"https://github.com/qss512985866","followers_url":"https://api.github.com/users/qss512985866/followers","following_url":"https://api.github.com/users/qss512985866/following{/other_user}","gists_url":"https://api.github.com/users/qss512985866/gists{/gist_id}","starred_url":"https://api.github.com/users/qss512985866/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/qss512985866/subscriptions","organizations_url":"https://api.github.com/users/qss512985866/orgs","repos_url":"https://api.github.com/users/qss512985866/repos","events_url":"https://api.github.com/users/qss512985866/events{/privacy}","received_events_url":"https://api.github.com/users/qss512985866/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-10-30T21:13:33Z","updated_at":"2016-10-30T21:13:33Z","closed_at":null,"body":"\r\n\r\nimport java.util.LinkedList;\r\nimport java.util.Random;\r\n\r\n\r\n/**\r\n   Maze class\r\n\r\n   Stores information about a maze and can find a path through the maze\r\n   (if there is one).\r\n   \r\n   Assumptions about structure of the maze, as given in mazeData, startLoc, and endLoc\r\n   (parameters to constructor), and the path:\r\n     -- no outer walls given in mazeData -- search assumes there is a virtual \r\n        border around the maze (i.e., the maze path can't go outside of the maze\r\n        boundaries)\r\n     -- start location for a path is maze coordinate startLoc\r\n     -- exit location is maze coordinate exitLoc\r\n     -- mazeData input is a 2D array of booleans, where true means there is a wall\r\n        at that location, and false means there isn't (see public FREE / WALL \r\n        constants below) \r\n     -- in mazeData the first index indicates the row. e.g., mazeData[row][col]\r\n     -- only travel in 4 compass directions (no diagonal paths)\r\n     -- can't travel through walls\r\n */\r\n\r\npublic class Maze {\r\n   \r\n   public static final boolean FREE = false; // Value of FREE and WALL\r\n   public static final boolean WALL = true;\r\n   private static final int FOR_INIT = 0; // Value for some initialization\r\n   private static final int FOR_MOVE = 1; // Value for recursive move\r\n   \r\n   private boolean myMaze[][];\r\n   private boolean visited[][];\r\n   private MazeCoord start,end;\r\n   private LinkedList<MazeCoord> myPath = new LinkedList<MazeCoord>();\r\n   /**\r\n      REPRESENTATION INVARIANT:\r\n      -- myMaze[][] is the boolean two-dimensional array for maze,the value of element should be\r\n      \t false(FREE) or true(WALL)\r\n      -- the number of rows of myMaze[][] should be as same as the number of the lines of binary data\r\n         in the input file\r\n      -- the number of columns of myMaze[][] should be as same as the number of the columns of binary data\r\n         in the input file\r\n      -- the number of rows of visited[][] should be as same as the number of the lines of binary data\r\n         in the input file\r\n      -- the number of columns of visited[][] should be as same as the number of the columns of binary data\r\n         in the input file\r\n      -- the initial value of every elements in visited[][] should be false(FREE)\r\n      -- if the point has been visited in the processing recursive step, change this element of the visited[][] to \r\n         true(WALL)\r\n      -- the initial value of myPath should be empty   \r\n      -- if we find a path, add the locations in the path to myPath recursively\r\n      -- start and end should be equal to the content of the input file\r\n   */\r\n\r\n   /**\r\n      Constructs a maze.\r\n      @param mazeData the maze to search.  See general Maze comments for what\r\n      goes in this array.\r\n      @param startLoc the location in maze to start the search (not necessarily on an edge)\r\n      @param endLoc the \"exit\" location of the maze (not necessarily on an edge)\r\n      PRE: 0 <= startLoc.getRow() < mazeData.length and 0 <= startLoc.getCol() < mazeData[0].length\r\n         and 0 <= endLoc.getRow() < mazeData.length and 0 <= endLoc.getCol() < mazeData[0].length\r\n\r\n    */\r\n   public Maze(boolean[][] mazeData, MazeCoord startLoc, MazeCoord endLoc)\r\n   {\r\n\t   myMaze = mazeData;\r\n\t   visited = new boolean[mazeData.length][mazeData[FOR_INIT].length];\r\n\t   for (int i = FOR_INIT; i < myMaze.length; i++)\r\n\t\t   for (int j=FOR_INIT; j < myMaze[FOR_INIT].length; j++){\r\n\t\t\t   visited[i][j] = FREE;\r\n\t\t   }\r\n\t   assert startLoc.getRow() >= 0 && startLoc.getRow() < mazeData.length;\r\n\t   assert startLoc.getCol() >= 0 && startLoc.getCol() < mazeData[FOR_INIT].length;\r\n\t   assert endLoc.getRow() >= 0 && endLoc.getRow() < mazeData.length;\r\n\t   assert endLoc.getCol() >= 0 && endLoc.getCol() < mazeData[FOR_INIT].length;\r\n\t   \r\n\t   start = startLoc;\r\n\t   end = endLoc;\r\n\r\n   }\r\n\r\n\r\n   /**\r\n      Returns the number of rows in the maze\r\n      @return number of rows\r\n    */\r\n   public int numRows() {\r\n       return myMaze.length;   \r\n   }\r\n\r\n   \r\n   /**\r\n      Returns the number of columns in the maze\r\n      @return number of columns\r\n    */   \r\n   public int numCols() {\r\n       return myMaze[FOR_INIT].length;   \r\n   } \r\n \r\n   \r\n   /**\r\n      Returns true iff there is a wall at this location\r\n      @param loc the location in maze coordinates\r\n      @return whether there is a wall here\r\n      PRE: 0 <= loc.getRow() < numRows() and 0 <= loc.getCol() < numCols()\r\n    */\r\n   public boolean hasWallAt(MazeCoord loc) {\r\n\t   \r\n\t   assert loc.getRow() >= 0 && loc.getRow() < myMaze.length;\r\n\t   assert loc.getCol() >= 0 && loc.getCol() < myMaze[FOR_INIT].length;\r\n\t  \r\n       return myMaze[loc.getRow()][loc.getCol()];   \r\n   }\r\n   \r\n\r\n   /**\r\n      Returns the entry location of this maze.\r\n    */\r\n   public MazeCoord getEntryLoc() {\r\n       return start;   \r\n   }\r\n   \r\n   \r\n   /**\r\n      Returns the exit location of this maze.\r\n    */\r\n   public MazeCoord getExitLoc() {\r\n       return end;\r\n   }\r\n\r\n   \r\n   /**\r\n      Returns the path through the maze. First element is starting location, and\r\n      last element is exit location.  If there was not path, or if this is called\r\n      before search, returns empty list.\r\n\r\n      @return the maze path\r\n    */\r\n   public LinkedList<MazeCoord> getPath() {\r\n\t   return myPath;   \r\n   }\r\n\r\n\r\n   /**\r\n      Find a path through the maze if there is one.  Client can access the\r\n      path found via getPath method.\r\n      @return whether path was found.\r\n    */\r\n   public boolean search()  {  \r\n\t   // if the start or end position has wall, we can't find the path\r\n       if (hasWallAt(start) || hasWallAt(end)){\r\n    \t   return false;\r\n       }\r\n       // if we find the path at the first time, save it and always return success\r\n       if (!myPath.isEmpty()){\r\n    \t   return true;\r\n       }\r\n       boolean result = searchRecur(start.getRow(),start.getCol());\r\n       return result;\r\n       \r\n   }\r\n   /**\r\n      Returns true iff there is a path through the input location (myRow, myCol)\r\n      @param myRow the x-coordinate of the location used to do next recursion\r\n      @param myCol the y-coordinate of the location used to do next recursion\r\n      @return whether there is a successful path\r\n      PRE: 0 <= myRow < numRows() and 0 <= myCol < numCols(), actually I do judgements \r\n      at the start\r\n    */\r\n   private boolean searchRecur(int myRow, int myCol){\r\n\t   if (myRow >= myMaze.length || myCol >= myMaze[FOR_INIT].length || myRow < 0 || myCol < 0){\r\n\t\t   return false;\r\n\t   }\r\n\t   // circle detect\r\n\t   if (visited[myRow][myCol]){\r\n\t\t   return false;\r\n\t   }\r\n\t   // if this is the end position, we find the path\r\n\t   if (myRow == end.getRow() && myCol == end.getCol()){\r\n\t\t   myPath.add(new MazeCoord(myRow,myCol));\r\n\t\t   visited[myRow][myCol] = WALL;\r\n\t\t   return true;\r\n\t   }\r\n\t   // if this is a wall, fail\r\n\t   if (myMaze[myRow][myCol]){\r\n\t\t   return false;\r\n\t   }\r\n\t   // do this to adjacent positions recursively\r\n\t   else{\r\n\t\t   boolean result = false;\r\n\t\t   visited[myRow][myCol] = WALL;\r\n\t\t   if (!result && searchRecur(myRow+FOR_MOVE, myCol)){\r\n\t\t\t   result = true;\r\n\t\t   }\r\n\t\t   if (!result && searchRecur(myRow-FOR_MOVE, myCol)){\r\n\t\t\t   result = true;\r\n\t\t   }\r\n\t\t   if (!result && searchRecur(myRow, myCol+FOR_MOVE)){\r\n\t\t\t   result = true;\r\n\t\t   }\r\n\t\t   if (!result && searchRecur(myRow, myCol-FOR_MOVE)){\r\n\t\t\t   result = true;\t\t   \r\n\t\t   }\r\n\t\t   visited[myRow][myCol] = FREE;\r\n\t\t   // add the correct locations to the path\r\n\t\t   if(result){\r\n\t\t\t   visited[myRow][myCol] = WALL;\r\n\t\t\t   myPath.add(new MazeCoord(myRow,myCol));\r\n\t\t\t   return result;\r\n\t\t   }\r\n\t\t   return false;\r\n\t   \t}\r\n\t   \r\n   }\r\n\r\n}\r\n"}}
{"actor":{"display_login":"qss512985866"}}