[ create a new paste ] login | about

Link: http://codepad.org/Cp1pUGrb    [ raw code | output | fork ]

mohit_at_codepad - C, pasted on Apr 4:
/*
 * Problem statement
 * Input file is a text file containing multiple test cases.
 * First line contains two numbers count of rows
 * and number of characters in each row.
 * Next row line contain num_of_character each.
 * Each character is forward or backward slash.
 * (If you are in a locale where backslash is
 * converted to currency sign like yen or wong,
 * backslash in my locale looks like horizontally flipped slash)
 * After a test case finishes, file contains the next text case.
 * Last test case is a blank test case (0 0)
 * Your program should read and visualize the rectengulary design,
 * and find the number of closed loops in design.
 * (For simplicity, there is no loop inside loop)
 * You should find the number of loops and area of largest loop.
 * (1 character takes 1 square unit)
 * For each test case (Except the last blank case),
 * print 1 line in output file. This line prints 2 numbers,
 * where first number is number of loops and the second number is
 * the area of largest loop.
 *
 * Sample Input File:
 * 6 4
 * \//\\/
 * \///\/
 * //\\/\
 * \/\///
 * 3 3
 * ///
 * \//
 * \\\
 * 0 0
 *
 * Sample output file for above case:
 * 2 16
 * 0 0
 *
 * For first case there are 2 loop with area 16 and 4
 *   /\
 *  / /
 * /  \
 * \/\/
 * and
 *
 *    /\
 *    \/
 *
 * For second case, there is no loop so both number of loop,
 * and area of largest loop are zero.
 * [Copy above designs into some editor with monospace font for better visualization]
 *
 *         /\
 * Area of \/ is 4 square units
 *
 * Limits:
 * 1. Input file contains less than 1000 test cases.
 * 2. Number of rows for a non blank test case is in limit 1-50 inclusive.
 * 3. Number of characters in each row is in limit 1-50 inclusive.
 */

#include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

//#define COMPILE_WITH_DEBUG_SUPPORT

#define LOCAL static  /* local variable or function */

void processDesign(char *in, char *out);

LOCAL void processFileDescriptors(FILE *fin, FILE *fout);
LOCAL void traverseLoops();
LOCAL void checkLoops(void);
LOCAL void tryLooping(int i, int j);
LOCAL void floodFill(int i, int j, int col);
LOCAL void createSlashMasks(void);
LOCAL int checkRight(int x, int y);
LOCAL int checkDown(int x, int y);

LOCAL int a = 0, b = 0;
LOCAL int nLoops = 0, szMaxLoop = 0;
LOCAL char designChars[2] = {'/', '\\'};
LOCAL char design[51][51] = {0}; /* This extra byte helps in debugging as string is zero terminated */
LOCAL int pixels[102][102] = {0};
LOCAL int backslashx[102][102] = {0};
LOCAL int backslashy[102][102] = {0};
LOCAL int slashx[102][102] = {0};
LOCAL int slashy[102][102] = {0};
LOCAL int loops[125] = {0};

LOCAL struct tagFFH_ {
  int x[102*102], y[102*102], curidx, lstidx;
} ffh;

void processDesign(char *in, char *out) {
  FILE *rd = NULL;
  FILE *wd = NULL;

  rd = fopen(in, "r");
  if( NULL == rd ) return;
  wd = fopen(out, "w");
  if(NULL == wd ) {
    fclose(rd);
    return;
  }
  processFileDescriptors(rd, wd);

  fclose(rd);
  fclose(wd);
}

LOCAL void processFileDescriptors(FILE *fin, FILE *fout) {
  int i = 0, j = 0;
  assert(fin && fout);

  createSlashMasks();
  do {
    nLoops = 0, szMaxLoop = 0;
    memset(design[0], 0, 51 * 51);
    memset(pixels[0], 0, 102 * 102 * sizeof pixels[0][0]);
    memset(loops, 0, 125 * sizeof loops[0]);
    nLoops = 0, szMaxLoop = 0;
    fscanf(fin, "%d %d", &a, &b);

    if(a + b == 0) break;
    for(i = 0; i < b; ++i)
    for(j = 0; j < a; ++j) {
      do { fscanf(fin, "%c", &design[i][j]); } while( isspace(design[i][j]) );
      assert(design[i][j] == designChars[0] || design[i][j] == designChars[1]);
    }
    traverseLoops();
#define COMPILE_WITH_DEBUG_SUPPORT
#ifdef COMPILE_WITH_DEBUG_SUPPORT
#define UNITS *10
    {
      FILE *debug_html = fopen("debug.html", "w");
      assert(NULL != debug_html);
      fprintf(debug_html, "<html xmlns:v=VML><head><style>v\\:*{behavior:url(#default#VML)}\n");
      fprintf(debug_html, "</style></head><body>\n");
      for(i = 0; i < 100; ++i) {
        fprintf(debug_html, "<v:line from=\"%d,%d\" to=\"%d,%d\" strokecolor=\"yellow\"/>\n",
          0 UNITS, i UNITS, 101 UNITS, i UNITS);
        fprintf(debug_html, "<v:line from=\"%d,%d\" to=\"%d,%d\" strokecolor=\"yellow\"/>\n",
          i UNITS, 0 UNITS, i UNITS, 101 UNITS);
      }

      for(i = 0; i < 100; ++i) {
        for(j = 0; j < 100; ++j) {
          if( !checkDown(i,j) ) {
            fprintf(debug_html, "<v:line from=\"%d,%d\" to=\"%d,%d\"/>\n",
              (i+1) UNITS, j UNITS, (i+1) UNITS, (j+1) UNITS);
          }
          if( !checkRight(i,j)) {
            fprintf(debug_html, "<v:line from=\"%d,%d\" to=\"%d,%d\"/>\n",
              i UNITS, (j+1) UNITS, (i+1) UNITS, (j+1) UNITS);
          }
        }
      }
      fprintf(debug_html, "</body></html>\n");
      fclose(debug_html);
    }
#endif
    fprintf(fout, "%d %d\n", nLoops, szMaxLoop);
  } while( a + b > 0);
}

LOCAL void traverseLoops(void) {
  floodFill(  0,   0, -1);
  checkLoops();
}

LOCAL void checkLoops(void) {
  int i = 0, j = 0, col = 0;
  for(i = 0; i < 100; ++i)
  for(j = 0; j < 100; ++j) {
    if(0 == pixels[i][j]) floodFill(i, j, ++col);
  }
  for(i = 0; i < 100; ++i)
  for(j = 0; j < 100; ++j) {
    int thisCol = pixels[i][j];
    if(-1 != thisCol) ++loops[thisCol-1];
  }
  nLoops = col;
  for(i = 0; i < col; ++i) if(szMaxLoop < loops[i]) szMaxLoop = loops[i];
}

LOCAL void floodFill(int i, int j, int col) {
  int canGoLeft = 0, canGoRight = 0, canGoUp = 0, canGoDown = 0;
  assert(0 == pixels[i][j]);
  pixels[i][j] = col;
  ffh.curidx = ffh.lstidx = 0;
  ffh.x[ffh.lstidx] = i;
  ffh.y[ffh.lstidx] = j;
  ++ffh.lstidx;
  while(ffh.curidx != ffh.lstidx) {
    int xx = ffh.x[ffh.curidx], yy = ffh.y[ffh.curidx];
    ++ffh.curidx;
    canGoLeft  = (0 != xx)
            && (0 == pixels[xx-1][yy])
            && ( 1 == checkRight(yy, xx-1) );
    canGoRight  = (99 != xx)
            && (0 == pixels[xx+1][yy])
            && 1 == checkRight(yy, xx);
    canGoUp    = (0 != yy)
            && (0 == pixels[xx][yy-1])
            && ( 1 == checkDown(yy-1, xx) );
    canGoDown  = (99 != yy)
            && (0 == pixels[xx][yy+1])
            && ( 1 == checkDown(yy, xx) );
#define CHECK_FF(X,Y) do {              \
            int x_ = X, y_ = Y;         \
            assert(0 == pixels[x_][y_]);\
            pixels[x_][y_] = col;       \
            ffh.x[ffh.lstidx] = x_;     \
            ffh.y[ffh.lstidx] = y_;     \
            ++ffh.lstidx;               \
          } while(0)
    if(canGoLeft)  CHECK_FF(xx-1, yy);
    if(canGoUp)   CHECK_FF(xx, yy-1);
    if(canGoRight)  CHECK_FF(xx+1, yy);
    if(canGoDown)  CHECK_FF(xx, yy+1);
  }
}

LOCAL int checkRight(int x, int y) {
  int xx = backslashx[x][y], yy = backslashy[x][y];
  if( (xx == -1) || (yy == -1) ) return 1;
  return ('\\' != design[xx][yy]);
}

LOCAL int checkDown(int x, int y) {
  int xx = slashx[x][y], yy = slashy[x][y];
  if( (xx == -1) || (yy == -1) ) return 1;
  return ('/' != design[xx][yy]);
}

LOCAL void createSlashMasks(void) {
  int i = 0, j = 0;
  int p = 0, q = 0, r = 0;

  for(i = 0; i < 102; ++i)
  for(j = 0; j < 102; ++j) {
    backslashx[i][j] = slashx[i][j] = backslashy[i][j] = slashy[i][j] = -1;
  }

  for(i = 0, j = 50-1; i < 50; ++i, --j) {
    p = i;
    q = j;
    for(r = 0; r < 50; ++p, ++q, ++r) {
      backslashx[p][q] = backslashx[p+1][q] = i;
      backslashy[p][q] = backslashy[p+1][q] = r;
      slashx[p][q] = slashx[p][q+1] = i;
      slashy[p][q] = slashy[p][q+1] = r;
    }
  }
}

int main(int argc, char *argv[]) {
  if(argc != 3) {
    printf("Please pass input test file and output result file name"
           " as command line argument.\n");
    return -1;
  }
  processDesign(argv[1], argv[2]);
  return 0;
}
/* EOF */


Output:
1
2
3
Please pass input test file and output result file name as command line argument.

Exited: ExitFailure 255


Create a new paste based on this one


Comments: