|
Programming Guru
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,835
Rep Power: 5 
|
SMAC #2 [06-08] - Trapped (Junior)
Attached to this post is the test data for trapped.
Trapped (Junior)
Junior was definitely harder this month, and quite a step up from beginner. But I thought an ASCII map question would be fun, so I hope it was a fun challenge for those who tried.
And as it turns out, a huge congratulations to everyone who submitted a solution to this problem. You all got perfect! I was not expecting that at all, so I was really pleased. Quite amazing, especially for a challenging problem like this.
Openloop's solution was like none I've ever seen in my years doing these things. It was quite creative, logical, and it works perfectly. He basically finds all of the horizontal and vertical components of the map, and then continuously merges them together to form all of the different rooms. However, I would not recommend doing something like this since it must have been a pain in the butt to code. Some huge eye-brow raising props goes to Openloop for this beast:
#include <iostream> #include <fstream> #include <string> #include <algorithm> // For sort() #include <functional> // For greater<int>( ) //using namespace std; #define WALL 'X' #define ROOM '.' #define HIGH_VALUE 99999 #define MAX_NODES 100 #define MAX_CONNS 100 #define MAX_ROWS 10 #define MAX_COLS 10 struct Node { int i, j; Node(){i = -1;j = -1;} Node(int x,int y){i = x; j = y;} void print(){ std::cout<<"("<<i<<","<<j<<"),";} bool operator==(const Node& rhs) const {return ((i==rhs.i)&&(j==rhs.j))?true:false;} //used by sort() bool operator<(const Node& rhs) const {return ((i<rhs.i)&&(j<rhs.j))?true:false;} //used by sort() }; struct Path { int value; Node node; }; class Connection { private: int nodeCount; public: bool active; Node node[MAX_NODES]; Connection(){nodeCount = 0; active = true;} bool operator<(const Connection& rhs)const {return ((nodeCount<rhs.nodeCount))?true:false;} //used by sort() bool operator>(const Connection& rhs) const {return ((nodeCount>rhs.nodeCount))?true:false;} //used by sort() and greater() void appendNode(Node n) { for(int i = 0; i < nodeCount; i++) if (node[i] == n) return; node[nodeCount] = n; nodeCount++; } static bool intersects(Connection &lhs, Connection &rhs) { for (int i = 0; i < lhs.nodeCount; i++) for (int j = 0; j < rhs.nodeCount; j++) if (lhs.node[i] == rhs.node[j]) return true; return false; } static Connection attachConnections(Connection& lhs, Connection& rhs) { Connection result = lhs; for (int i = 0; i < rhs.nodeCount; i++) result.appendNode(rhs.node[i]); return result; } int weigth(){return nodeCount;} void print(){for(int a = 0; a < weigth(); a++) node[a].print();} }; int main() { int w, h; char floor[MAX_ROWS][MAX_COLS]; Connection hConn[MAX_CONNS], vConn[MAX_CONNS]; std::ifstream fin("trapped.in"); std::ofstream fout("trapped.out"); if (!fin || !fout) {std::cout<<"IO ERROR!\n"; return 12;} //Read floor dimentions fin>>w>>h; //Load the floorplan for (int i = 0; i < h; i++){ for (int j = 0; j < w; j++){ fin>>floor[i][j]; std::cout<<floor[i][j]; } std::cout<<"\n"; } int hConCount = -1, vConCount = -1; bool hActiveConn = false, vActiveConn = false; //traverse array horizontally & vertically to discover connections for (int i = 0; i < h; i++){ for (int j = 0; j < w; j++){ //horizontal if (floor[i][j] == ROOM){ if (!hActiveConn){ //start new connection hConCount++; hActiveConn = true; } hConn[hConCount].appendNode(Node(i,j)); }else{ //disconnect hActiveConn = false; } //vertical if (floor[j][i] == ROOM){ if (!vActiveConn){ //start new connection vConCount++; vActiveConn = true; } vConn[vConCount].appendNode(Node(j,i)); //add the room coordinates to this connection }else{ //disconnect vActiveConn = false; } } hActiveConn = false; //end of row, close connection vActiveConn = false; //end of column, close connection } hConCount++; vConCount++; //intersect horizontal and vertical connections into the iConn array to build the rooms std::sort(hConn, hConn + hConCount, std::greater<Connection>()); std::sort(vConn, vConn + vConCount, std::greater<Connection>()); int iConCount = 0; Connection iConn[100]; for(int m = 0; m < hConCount; m++) for(int n = 0; n < vConCount; n++) if (Connection::intersects(hConn[m],vConn[n])) iConn[iConCount++] = Connection::attachConnections(hConn[m],vConn[n]); //Even though we intersected the connection, there is a possibility that two or more connection might still intersect. //Keep looping and intersecting iConn connections with each other until no more intersections are found. std::sort(iConn, iConn + iConCount, std::greater<Connection>()); bool intersectFound = true; while (intersectFound) { intersectFound = false; for(int i = 0; i < iConCount; i++){ for(int j = i+1; j < iConCount && iConn[i].active; j++){ if (iConn[i].active && iConn[j].active && Connection::intersects(iConn[i],iConn[j])) { iConn[i] = Connection::attachConnections(iConn[i],iConn[j]); iConn[j].active = false; intersectFound = true; } } } } //Now that we have the room configuration figured out(in the form of connections), //we can go to figure out the size of the smallest room //Also print the room configuration int roomAir = HIGH_VALUE; int minRoomAir = HIGH_VALUE; std::cout<<"Room configuration(s) follow:\n"; int roomNum = 1; for(int i = 0; i < iConCount; i++) { if (iConn[i].active) { std::cout<<"Room #"<<roomNum++<<": "; iConn[i].print(); std::cout<<"\n\n"; roomAir = iConn[i].weigth() * 5; minRoomAir = std::min(minRoomAir,roomAir); } } fout<<(minRoomAir==HIGH_VALUE?0:minRoomAir)<<"\n"; fin.close(); fout.close(); std::cout<<"Press ENTER To Exit\n"; std::getchar(); return 0; }
Titanium Decoy must have cheated, because he copied my code almost exactly.
Andrew, our third perfect, did things a bit differently with his use of globals, but still got the job done.
Jimbo, the fourth and final perfect, demonstrated his solid understanding of graph theory by using a Breadth-First Search (BFS) to fill each room. The BFS is no faster than a DFS here, but it certainly looks cool.
Knowing how and when to do a BFS may or may not PROVE TO BE USEFUL for one of July's challenges!!
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace SMAC2_Junior { class Program { /// strategy: /// create a matrix to represent the floor plan /// for each open space, do a BFS on it's surrounding open spaces to get the size of the room /// when finished with the room, save the result if it's the smallest encountered yet /// if an unused space still exists, repeat from the for loop static void Main(string[] args) { StreamReader swapIn = null; StreamWriter swapOut = null; try { swapIn = new StreamReader("swap.in"); swapOut = new StreamWriter("swap.out"); string buffer = swapIn.ReadLine(); int w, h; string[] nums = buffer.Split(" ".ToCharArray()); w = int.Parse(nums[0]); h = int.Parse(nums[1]); char[][] map = new char[h][]; // read in map for (int i = 0; i < h; i++) { string line = swapIn.ReadLine(); if (line.Length != w) { throw new InvalidDataException(String.Format("Line width is incorrect. Expected width: {0}; Actual string: {1}", w, line)); } map[i] = new char[w]; line.ToCharArray().CopyTo(map[i], 0); } #if DEBUG Console.WriteLine("Read map as: "); for (int i = 0; i < h; i++) { Console.WriteLine(map[i]); } #endif int smallestRoom = int.MaxValue; // now check them all for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (map[i][j] == RoomState.Unchecked) { int size = getRoomSize(map, i, j); #if DEBUG Console.WriteLine("Found room of size {0}", size); #endif if (size < smallestRoom) { smallestRoom = size; } } } } // output result * 5 #if DEBUG Console.WriteLine(smallestRoom * 5); #endif swapOut.WriteLine(smallestRoom * 5); } catch (Exception e) { Console.WriteLine(String.Format("Error encountered, aborting. Error: [{0}]", e.ToString())); } finally { if (swapIn != null) { swapIn.Close(); swapIn = null; } if (swapOut != null) { swapOut.Close(); swapOut = null; } } } private static int getRoomSize(char[][] map, int y, int x) { if (map[y][x] != RoomState.Unchecked) { return int.MaxValue; } HashSet<CoordinatePair> toCheck = new HashSet<CoordinatePair>(); toCheck.Add(new CoordinatePair(x, y)); int size = 0; CoordinatePair current; while (toCheck.Count > 0) { current = toCheck.First(); toCheck.Remove(current); if (map[current.Y][current.X] != RoomState.Unchecked) { continue; } // update for this square size++; map[current.Y][current.X] = RoomState.Checked; CoordinatePair temp; temp = new CoordinatePair(current.X, current.Y - 1); if (temp.Y > 0 && map[temp.Y][temp.X] == RoomState.Unchecked) toCheck.Add(temp); // check down temp = new CoordinatePair(current.X, current.Y + 1); if (y < map.Length - 1 && map[temp.Y][temp.X] == RoomState.Unchecked) toCheck.Add(temp); temp = new CoordinatePair(current.X - 1, current.Y); if (temp.X > 0 && map[temp.Y][temp.X] == RoomState.Unchecked) toCheck.Add(temp); temp = new CoordinatePair(current.X + 1, current.Y); if (temp.X < map[temp.Y].Length && map[temp.Y][temp.X] == RoomState.Unchecked) toCheck.Add(temp); } return size; } static class RoomState { public const char Wall = 'X'; public const char Unchecked = '.'; public const char Checked = 'O'; } class CoordinatePair { public int X; public int Y; public CoordinatePair(int x, int y) { X = x; Y = y; } } } }
So now, on to the easy solution.
The key here is to not worry about how many rooms there are, or the shape of each individual room.
All you really need is a "fill" function that accepts an (x,y) co-ordinate and returns the size of the room at that point.
Then repeatedly call the fill function for every possible co-ordinate, and output the smallest non-zero size.
Writing the fill function is the hard part, since rooms can span and branch out in all directions from a particular point.
For example, if you were to start the fill function at "@", the room branches off into three different paths which are all part of the same room.
XXXXXXXX
XXXX.XXX
XXXX.XXX
X...@XXX
XXXX.XXX
XXXX.XXX
XXXXXXXX
This idea of "branching" makes it suitable to use recursion.
Recursion will automatically take care of the way a room can branch out into many different directions.
I won't bother proving this fact. Explaining recursion is even more difficult than learning it. But if you're interested, I'm sure someone here is willing to help you understand the logic.
A rough version of our function might look something like this:
void fill(int x, int y) {
if(x<0||y<0||x>=w||y>=h) return;
if(grid[y][x] == 'X') return;
fill(x+1,y);
fill(x,y+1);
fill(x-1,y);
fill(x,y-1);
}
But there's quite a big problem here, and its name is Infinite Recursion. Nothing's stopping fill from recursing back to where it was initially, which would result in everything repeating over and over again until the sun explodes.
The trick is to replace the space with a wall (X) once it's been visited. Consequently, we only "look" at each space once. Since we only need to count each space once, that's perfect. Again, the proof behind this takes a solid understanding of recursion.
There's only one more thing that needs taking care of, and that's the actual counting of spaces in the room. By recursive definition, the number of open spaces in a room is 1 + the number of open spaces in all of its adjacent neighbours.
Combine all of that together, and you've got your fill function:
int fill(int x, int y) {
if(x<0||y<0||x>=w||y>=h) return 0;
if(grid[y][x] == 'X') return 0;
grid[y][x] = 'X';
return 1 + fill(x+1,y) + fill(x,y+1) + fill(x-1,y) + fill(x,y-1);
}
And here's the solution:
#include <stdio.h> #define MAX 11 char grid[MAX][MAX]; int w, h; int fill(int x, int y) { if(x<0||y<0||x>=w||y>=h) return 0; if(grid[y][x] == 'X') return 0; grid[y][x] = 'X'; return 1 + fill(x+1,y) + fill(x,y+1) + fill(x-1,y) + fill(x,y-1); } int main() { int vol=MAX*MAX; freopen("trapped.in", "rt", stdin); freopen("trapped.out", "wt", stdout); scanf("%d %d", &w, &h); for(int y=0; y<h; y++) scanf("%s", grid[y]); for(int x=0; x<w; x++) for(int y=0; y<h; y++) if(int r=fill(x,y)) vol<?=r; printf("%d\n", vol*5); return 0; }
|