Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * main.cpp
- *
- * Created on: 15 Oct 2011
- * Author: thomas
- */
- #include <string.h>
- #include <stdlib.h>
- #include <stack>
- #include <iostream>
- #define VERBOSE 0
- using namespace std;
- struct Point
- {
- int x, y;
- Point(int x, int y)
- : x(x), y(y)
- {}
- };
- static unsigned char currentMap[500][500];
- static int rowWidths[500];
- static int currentRowCount = 0;
- static stack<Point> doors;
- static int currentRoomNumber = (int)'0';
- static int currentRoomCount = 0;
- bool isValidDoor(Point & door);
- void printCurrent();
- void floodFill(Point & seed);
- Point findValidSpace(Point & centrePoint);
- static int bestCount, bestFloor;
- int main()
- {
- int numFloors;
- cin >> numFloors;
- string row;
- getline(cin, row);
- bestCount = 0;
- bestFloor = 0;
- for(int i = 0; i < numFloors; i++)
- {
- currentRowCount = 0;
- do
- {
- getline(cin, row);
- rowWidths[currentRowCount] = row.length();
- memcpy(¤tMap[currentRowCount++][0], row.c_str(), row.length() + 1);
- }
- while(row.compare("\n") != -1);
- Point superSeed(0, 0);
- for(int j = 0; j < currentRowCount; j++)
- {
- for(int k = 0; k < rowWidths[j]; k++)
- {
- if(currentMap[j][k] != '*')
- {
- superSeed.x = j;
- superSeed.y = k;
- j = currentRowCount;
- break;
- }
- }
- }
- currentRoomCount = 0;
- currentRoomNumber = (int)'0';
- floodFill(superSeed);
- #if VERBOSE
- printCurrent();
- cout << currentRoomCount << endl;
- #endif
- if(currentRoomCount > bestCount)
- {
- bestCount = currentRoomCount;
- bestFloor = i + 1;
- }
- currentRoomNumber++;
- while(doors.size() > 0)
- {
- Point & currentDoor = doors.top();
- doors.pop();
- if(!isValidDoor(currentDoor))
- {
- continue;
- }
- currentRoomCount = 0;
- Point newSeed = findValidSpace(currentDoor);
- floodFill(newSeed);
- #if VERBOSE
- printCurrent();
- cout << currentRoomCount << endl;
- #endif
- if(currentRoomCount > bestCount)
- {
- bestCount = currentRoomCount;
- bestFloor = i + 1;
- }
- currentRoomNumber++;
- }
- }
- cout << bestFloor << " " << bestCount << endl;
- }
- void floodFill(Point & seed)
- {
- stack<Point> myStack;
- myStack.push(seed);
- while(myStack.size() > 0)
- {
- Point & p = myStack.top();
- myStack.pop();
- int x = p.x;
- int y = p.y;
- if (y < 0 || y > rowWidths[x] - 1 || x < 0 || x > currentRowCount - 1)
- {
- continue;
- }
- unsigned char val = currentMap[x][y];
- if(val == '*' || val == currentRoomNumber)
- {
- continue;
- }
- else if(val == 'D')
- {
- doors.push(p);
- currentMap[x][y] = '*';
- }
- else if(val == 'C' || val == ' ' || val == 'S')
- {
- if(val == 'C')
- {
- currentRoomCount++;
- }
- currentMap[x][y] = currentRoomNumber;
- myStack.push(Point(x + 1, y));
- myStack.push(Point(x - 1, y));
- myStack.push(Point(x, y + 1));
- myStack.push(Point(x, y - 1));
- }
- }
- }
- bool isValidDoor(Point & door)
- {
- return (currentMap[door.x + 1][door.y] == ' ' ||
- currentMap[door.x - 1][door.y] == ' ' ||
- currentMap[door.x + 1][door.y + 1] == ' ' ||
- currentMap[door.x + 1][door.y - 1] == ' ' ||
- currentMap[door.x - 1][door.y + 1] == ' ' ||
- currentMap[door.x - 1][door.y - 1] == ' ' ||
- currentMap[door.x][door.y + 1] == ' ' ||
- currentMap[door.x][door.y - 1] == ' ' ||
- currentMap[door.x + 1][door.y] == 'S' ||
- currentMap[door.x - 1][door.y] == 'S' ||
- currentMap[door.x + 1][door.y + 1] == 'S' ||
- currentMap[door.x + 1][door.y - 1] == 'S' ||
- currentMap[door.x - 1][door.y + 1] == 'S' ||
- currentMap[door.x - 1][door.y - 1] == 'S' ||
- currentMap[door.x][door.y + 1] == 'S' ||
- currentMap[door.x][door.y - 1] == 'S' ||
- currentMap[door.x + 1][door.y] == 'C' ||
- currentMap[door.x - 1][door.y] == 'C' ||
- currentMap[door.x + 1][door.y + 1] == 'C' ||
- currentMap[door.x + 1][door.y - 1] == 'C' ||
- currentMap[door.x - 1][door.y + 1] == 'C' ||
- currentMap[door.x - 1][door.y - 1] == 'C' ||
- currentMap[door.x][door.y + 1] == 'C' ||
- currentMap[door.x][door.y - 1] == 'C');
- }
- Point findValidSpace(Point & centrePoint)
- {
- if(currentMap[centrePoint.x + 1][centrePoint.y] == ' ' ||
- currentMap[centrePoint.x + 1][centrePoint.y] == 'S' ||
- currentMap[centrePoint.x + 1][centrePoint.y] == 'C')
- {
- return Point(centrePoint.x + 1, centrePoint.y);
- }
- if(currentMap[centrePoint.x + 1][centrePoint.y + 1] == ' ' ||
- currentMap[centrePoint.x + 1][centrePoint.y + 1] == 'S' ||
- currentMap[centrePoint.x + 1][centrePoint.y + 1] == 'C')
- {
- return Point(centrePoint.x + 1, centrePoint.y + 1);
- }
- if(currentMap[centrePoint.x + 1][centrePoint.y - 1] == ' ' ||
- currentMap[centrePoint.x + 1][centrePoint.y - 1] == 'S' ||
- currentMap[centrePoint.x + 1][centrePoint.y - 1] == 'C')
- {
- return Point(centrePoint.x + 1, centrePoint.y - 1);
- }
- if(currentMap[centrePoint.x - 1][centrePoint.y] == ' ' ||
- currentMap[centrePoint.x - 1][centrePoint.y] == 'S' ||
- currentMap[centrePoint.x - 1][centrePoint.y] == 'C')
- {
- return Point(centrePoint.x - 1, centrePoint.y);
- }
- if(currentMap[centrePoint.x - 1][centrePoint.y + 1] == ' ' ||
- currentMap[centrePoint.x - 1][centrePoint.y + 1] == 'S' ||
- currentMap[centrePoint.x - 1][centrePoint.y + 1] == 'C')
- {
- return Point(centrePoint.x - 1, centrePoint.y + 1);
- }
- if(currentMap[centrePoint.x - 1][centrePoint.y - 1] == ' ' ||
- currentMap[centrePoint.x - 1][centrePoint.y - 1] == 'S' ||
- currentMap[centrePoint.x - 1][centrePoint.y - 1] == 'C')
- {
- return Point(centrePoint.x - 1, centrePoint.y - 1);
- }
- if(currentMap[centrePoint.x][centrePoint.y + 1] == ' ' ||
- currentMap[centrePoint.x][centrePoint.y + 1] == 'S' ||
- currentMap[centrePoint.x][centrePoint.y + 1] == 'C')
- {
- return Point(centrePoint.x, centrePoint.y + 1);
- }
- if(currentMap[centrePoint.x][centrePoint.y - 1] == ' ' ||
- currentMap[centrePoint.x][centrePoint.y - 1] == 'S' ||
- currentMap[centrePoint.x][centrePoint.y - 1] == 'C')
- {
- return Point(centrePoint.x, centrePoint.y - 1);
- }
- //Bleh
- return Point(-1, -1);
- }
- void printCurrent()
- {
- for(int j = 0; j < currentRowCount; j++)
- {
- for(int k = 0; k < rowWidths[j]; k++)
- {
- cout << currentMap[j][k];
- }
- cout << endl;
- }
- }
Add Comment
Please, Sign In to add comment