codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/* * 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 */
Private
[
?
]
Run code
Submit