Indian National Olympiad in Informatics, 2003

Solution to Question 1, Chambers in a Castle

IARCS home > OLYMPIAD > Archives
  • The idea

    Initially, all non wall squares are marked 0. As we visit rooms, we convert squares from 0 to 1. We maintain two variables, one to keep track of the number of chambers. and one to keep track of the size of the largest chamber.

    Scan the floor plan of the castle from top to bottom, left to right. Each time you see a square marked 0, this is a new chamber. Increment the number of chambers. Recursively explore the neighbourhood of this chamber, determine its size and update the maximum size seen so far, if necessary.

  • A C program for this problem
  • Some test inputs ...
  • ... and corresponding outputs



Copyright (c) IARCS 2003-2018;   Last Updated: 23 May, 2003