// Two-star problem // Problem 572 Oil Deposits /* This program is written by Prof. Chua-Huang Huang Department of Information Engineering and Computer Science Feng Chia University Taichung, Taiwan Disclaimer: The programming problem is downloaded from UVa Online Judge (https://uva.onlinejudge.org/). The program solution is provided for helping students to prepare Collegiate Programming Examination (CPE). The author does not guarantee the program is completely correct to pass UVa Online Judge platform or CPE examination platform. This program is not intended for a student to copy only. He/She should practice the programming problem himself/herself. Only use the program solution as a reference. The author is not responsible if the program causes any damage of your computer or personal properties. No commercial use of this program is allowed without the author's written permission. */ #include #include // Use digits and letters to mark plot, maximum 62 deposits. // The purpose of different is for displaying the deposits mark, though it is // not required in the problem. void new_pocket(char *plot, char *deposit) { *plot = *deposit; // Mark the new pocket. if ((*deposit)<'9') (*deposit)++; // Set the next deposit mark as the next digit. else if ((*deposit)=='9') *deposit = 'A'; // Set the next deposit mark as letter 'A'. else if ((*deposit)<'Z') (*deposit)++; // Set the next deposit mark as the next letter. else if ((*deposit)=='Z') *deposit = 'a'; // Set the next deposit mark as letter 'a'. else (*deposit)++; // Set the next deposit mark as the next letter. if ((*deposit)=='z'+1) *deposit = '0'; // More than 62 deposits, start mark from '0' again. } /* Mark the neighbors as the same mark. Each plot has maximum eight neighbors. Neighborhood marking will propagate the mark to all possible neighbors recursively. grid: the pointer to the two-dimensional grid. m, n: number of rows and columns of the grid. i, j: row and column index of the plot. mark: mark of the pocket. */ void mark_neighbors(char grid[100][101], int m, int n, int i, int j, char mark) { if (i>0) { // Exclude the top row. if (j>0 && grid[i-1][j-1]=='@') { grid[i-1][j-1] = mark; // upper-left plot mark_neighbors(grid, m, n, i-1, j-1, mark); // Propagate the mark to neighbors. } if (grid[i-1][j]=='@') { grid[i-1][j] = mark; // upper plot mark_neighbors(grid, m, n, i-1, j, mark); // Propagate the mark to neighbors. } if (j0 && grid[i+1][j-1]=='@') { grid[i+1][j-1] = mark; // lower-left plot mark_neighbors(grid, m, n, i+1, j-1, mark); // Propagate the mark to neighbors. } if (grid[i+1][j]=='@') { grid[i+1][j] = mark; // lower plot mark_neighbors(grid, m, n, i+1, j, mark); // Propagate the mark to neighbors. } if (j0 && grid[i][j-1]=='@') { grid[i][j-1] = mark; // left plot mark_neighbors(grid, m, n, i, j-1, mark); // Propagate the mark to neighbors. } if (j0 && j>0 && grid[i-1][j-1]!='*' && grid[i-1][j-1]!='@') // check upper-left plot grid[i][j] = grid[i-1][j-1]; // Mark same pocket as the upper-left plot. else if (i>0 && grid[i-1][j]!='*' && grid[i-1][j]!='@') // check upper plot grid[i][j] = grid[i-1][j]; // Mark same pocket as the upper plot. else if (i>0 && j0 && grid[i+1][j-1]!='*' && grid[i+1][j-1]!='@') // check lower-left plot grid[i][j] = grid[i+1][j-1]; // Mark same pocket as the lower-left plot. else if (i0 && grid[i][j-1]!='*' && grid[i][j-1]!='@') // check left plot grid[i][j] = grid[i][j-1]; // Mark same pocket as the left plot. else if (j