Guest User

Untitled

a guest
Jan 22nd, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.36 KB | None | 0 0
  1. /*
  2.  * main.cpp
  3.  *
  4.  *  Created on: 15 Oct 2011
  5.  *      Author: thomas
  6.  */
  7.  
  8. #include <string.h>
  9. #include <stdlib.h>
  10. #include <stack>
  11. #include <iostream>
  12.  
  13. #define VERBOSE 0
  14.  
  15. using namespace std;
  16.  
  17. struct Point
  18. {
  19.     int x, y;
  20.  
  21.     Point(int x, int y)
  22.     : x(x), y(y)
  23.     {}
  24. };
  25.  
  26. static unsigned char currentMap[500][500];
  27. static int rowWidths[500];
  28. static int currentRowCount = 0;
  29.  
  30. static stack<Point> doors;
  31.  
  32. static int currentRoomNumber = (int)'0';
  33. static int currentRoomCount = 0;
  34.  
  35. bool isValidDoor(Point & door);
  36. void printCurrent();
  37. void floodFill(Point & seed);
  38. Point findValidSpace(Point & centrePoint);
  39.  
  40. static int bestCount, bestFloor;
  41.  
  42. int main()
  43. {
  44.     int numFloors;
  45.     cin >> numFloors;
  46.  
  47.     string row;
  48.  
  49.     getline(cin, row);
  50.  
  51.     bestCount = 0;
  52.     bestFloor = 0;
  53.  
  54.     for(int i = 0; i < numFloors; i++)
  55.     {
  56.         currentRowCount = 0;
  57.  
  58.         do
  59.         {
  60.             getline(cin, row);
  61.             rowWidths[currentRowCount] = row.length();
  62.             memcpy(&currentMap[currentRowCount++][0], row.c_str(), row.length() + 1);
  63.         }
  64.         while(row.compare("\n") != -1);
  65.  
  66.         Point superSeed(0, 0);
  67.  
  68.         for(int j = 0; j < currentRowCount; j++)
  69.         {
  70.             for(int k = 0; k < rowWidths[j]; k++)
  71.             {
  72.                if(currentMap[j][k] != '*')
  73.                {
  74.                    superSeed.x = j;
  75.                    superSeed.y = k;
  76.                    j = currentRowCount;
  77.                    break;
  78.                }
  79.             }
  80.         }
  81.  
  82.         currentRoomCount = 0;
  83.         currentRoomNumber = (int)'0';
  84.  
  85.         floodFill(superSeed);
  86.  
  87. #if VERBOSE
  88.         printCurrent();
  89.         cout << currentRoomCount << endl;
  90. #endif
  91.  
  92.         if(currentRoomCount > bestCount)
  93.         {
  94.             bestCount = currentRoomCount;
  95.             bestFloor = i + 1;
  96.         }
  97.  
  98.         currentRoomNumber++;
  99.  
  100.         while(doors.size() > 0)
  101.         {
  102.             Point & currentDoor = doors.top();
  103.  
  104.             doors.pop();
  105.  
  106.             if(!isValidDoor(currentDoor))
  107.             {
  108.                 continue;
  109.             }
  110.  
  111.             currentRoomCount = 0;
  112.  
  113.             Point newSeed = findValidSpace(currentDoor);
  114.  
  115.             floodFill(newSeed);
  116.  
  117. #if VERBOSE
  118.             printCurrent();
  119.             cout << currentRoomCount << endl;
  120. #endif
  121.  
  122.             if(currentRoomCount > bestCount)
  123.             {
  124.                 bestCount = currentRoomCount;
  125.                 bestFloor = i + 1;
  126.             }
  127.  
  128.             currentRoomNumber++;
  129.         }
  130.     }
  131.  
  132.     cout << bestFloor << " " << bestCount << endl;
  133. }
  134.  
  135. void floodFill(Point & seed)
  136. {
  137.     stack<Point> myStack;
  138.     myStack.push(seed);
  139.  
  140.     while(myStack.size() > 0)
  141.     {
  142.         Point & p = myStack.top();
  143.         myStack.pop();
  144.         int x = p.x;
  145.         int y = p.y;
  146.  
  147.         if (y < 0 || y > rowWidths[x] - 1 || x < 0 || x > currentRowCount - 1)
  148.         {
  149.             continue;
  150.         }
  151.  
  152.         unsigned char val = currentMap[x][y];
  153.  
  154.         if(val == '*' || val == currentRoomNumber)
  155.         {
  156.             continue;
  157.         }
  158.         else if(val == 'D')
  159.         {
  160.             doors.push(p);
  161.             currentMap[x][y] = '*';
  162.         }
  163.         else if(val == 'C' || val == ' ' || val == 'S')
  164.         {
  165.             if(val == 'C')
  166.             {
  167.                 currentRoomCount++;
  168.             }
  169.  
  170.             currentMap[x][y] = currentRoomNumber;
  171.  
  172.             myStack.push(Point(x + 1, y));
  173.             myStack.push(Point(x - 1, y));
  174.             myStack.push(Point(x, y + 1));
  175.             myStack.push(Point(x, y - 1));
  176.         }
  177.     }
  178. }
  179.  
  180. bool isValidDoor(Point & door)
  181. {
  182.     return (currentMap[door.x + 1][door.y] == ' ' ||
  183.             currentMap[door.x - 1][door.y] == ' ' ||
  184.             currentMap[door.x + 1][door.y + 1] == ' ' ||
  185.             currentMap[door.x + 1][door.y - 1] == ' ' ||
  186.             currentMap[door.x - 1][door.y + 1] == ' ' ||
  187.             currentMap[door.x - 1][door.y - 1] == ' ' ||
  188.             currentMap[door.x][door.y + 1] == ' ' ||
  189.             currentMap[door.x][door.y - 1] == ' ' ||
  190.             currentMap[door.x + 1][door.y] == 'S' ||
  191.             currentMap[door.x - 1][door.y] == 'S' ||
  192.             currentMap[door.x + 1][door.y + 1] == 'S' ||
  193.             currentMap[door.x + 1][door.y - 1] == 'S' ||
  194.             currentMap[door.x - 1][door.y + 1] == 'S' ||
  195.             currentMap[door.x - 1][door.y - 1] == 'S' ||
  196.             currentMap[door.x][door.y + 1] == 'S' ||
  197.             currentMap[door.x][door.y - 1] == 'S' ||
  198.             currentMap[door.x + 1][door.y] == 'C' ||
  199.             currentMap[door.x - 1][door.y] == 'C' ||
  200.             currentMap[door.x + 1][door.y + 1] == 'C' ||
  201.             currentMap[door.x + 1][door.y - 1] == 'C' ||
  202.             currentMap[door.x - 1][door.y + 1] == 'C' ||
  203.             currentMap[door.x - 1][door.y - 1] == 'C' ||
  204.             currentMap[door.x][door.y + 1] == 'C' ||
  205.             currentMap[door.x][door.y - 1] == 'C');
  206. }
  207.  
  208. Point findValidSpace(Point & centrePoint)
  209. {
  210.     if(currentMap[centrePoint.x + 1][centrePoint.y] == ' ' ||
  211.        currentMap[centrePoint.x + 1][centrePoint.y] == 'S' ||
  212.        currentMap[centrePoint.x + 1][centrePoint.y] == 'C')
  213.     {
  214.         return Point(centrePoint.x + 1, centrePoint.y);
  215.     }
  216.  
  217.     if(currentMap[centrePoint.x + 1][centrePoint.y + 1] == ' ' ||
  218.        currentMap[centrePoint.x + 1][centrePoint.y + 1] == 'S' ||
  219.        currentMap[centrePoint.x + 1][centrePoint.y + 1] == 'C')
  220.     {
  221.         return Point(centrePoint.x + 1, centrePoint.y + 1);
  222.     }
  223.  
  224.     if(currentMap[centrePoint.x + 1][centrePoint.y - 1] == ' ' ||
  225.        currentMap[centrePoint.x + 1][centrePoint.y - 1] == 'S' ||
  226.        currentMap[centrePoint.x + 1][centrePoint.y - 1] == 'C')
  227.     {
  228.         return Point(centrePoint.x + 1, centrePoint.y - 1);
  229.     }
  230.  
  231.     if(currentMap[centrePoint.x - 1][centrePoint.y] == ' ' ||
  232.        currentMap[centrePoint.x - 1][centrePoint.y] == 'S' ||
  233.        currentMap[centrePoint.x - 1][centrePoint.y] == 'C')
  234.     {
  235.         return Point(centrePoint.x - 1, centrePoint.y);
  236.     }
  237.  
  238.     if(currentMap[centrePoint.x - 1][centrePoint.y + 1] == ' ' ||
  239.        currentMap[centrePoint.x - 1][centrePoint.y + 1] == 'S' ||
  240.        currentMap[centrePoint.x - 1][centrePoint.y + 1] == 'C')
  241.     {
  242.         return Point(centrePoint.x - 1, centrePoint.y + 1);
  243.     }
  244.  
  245.     if(currentMap[centrePoint.x - 1][centrePoint.y - 1] == ' ' ||
  246.        currentMap[centrePoint.x - 1][centrePoint.y - 1] == 'S' ||
  247.        currentMap[centrePoint.x - 1][centrePoint.y - 1] == 'C')
  248.     {
  249.         return Point(centrePoint.x - 1, centrePoint.y - 1);
  250.     }
  251.  
  252.     if(currentMap[centrePoint.x][centrePoint.y + 1] == ' ' ||
  253.        currentMap[centrePoint.x][centrePoint.y + 1] == 'S' ||
  254.        currentMap[centrePoint.x][centrePoint.y + 1] == 'C')
  255.     {
  256.         return Point(centrePoint.x, centrePoint.y + 1);
  257.     }
  258.  
  259.     if(currentMap[centrePoint.x][centrePoint.y - 1] == ' ' ||
  260.        currentMap[centrePoint.x][centrePoint.y - 1] == 'S' ||
  261.        currentMap[centrePoint.x][centrePoint.y - 1] == 'C')
  262.     {
  263.         return Point(centrePoint.x, centrePoint.y - 1);
  264.     }
  265.  
  266.     //Bleh
  267.     return Point(-1, -1);
  268. }
  269.  
  270. void printCurrent()
  271. {
  272.     for(int j = 0; j < currentRowCount; j++)
  273.     {
  274.         for(int k = 0; k < rowWidths[j]; k++)
  275.         {
  276.             cout << currentMap[j][k];
  277.         }
  278.         cout << endl;
  279.     }
  280. }
Add Comment
Please, Sign In to add comment