Description
- Your program reads one text file:
- txt
- Your program creates a text file:
- txt
- Your program solves the following problem:
- You are given a water level information L. Condition: 0<L<
- You are given a terrain information (elevation matrix M). Condition: 0≤M[i][j]<128∀i,j<
- Calculate how many islands are formed and return a coordinate value for each island.
- Definition of an island: An island is the collection of terrain points( elevation values M[i][j]), above water( greater than L value), from which you can find a path to any other without having to pass the path through water.
- Definition of a path: A path is an ordered set of points where successive points have either their X coordinates the same and their Y coordinates different only by one in magnitude (so can be y – 1 or y + 1); or have their Y coordinates the same and have their X coordinates different only by one in magnitude (so can be x – 1 or x + 1). But not both of them: in other words they have to touch either in the X direction or in the Y direction, and not in the diagonal.
- If a piece of terrain is partially (or fully) located (touching) at the edge(s) of the 512 × 512 grid, still it will count as an island.
input.txt
- First line is a single integer. (The L value)
- The rest of the file has 262144 integers. Skip all the whitespace and read all of these integers and create a 512×512 matrix. Integers are listed in row-order.
output.txt
- The first line is an integer (number of islands)
- Each line after the first line holds coordinate information of a point on an island. (single point for each island)
- Example: Here there are 5 islands. (#… are comments, which are not printed.)
5 | |
x_coordinate1 y_coordinate1 | #coordinate of a point which is on island1 |
x_coordinate2 y_coordinate2 | #coordinate of a point which is on island2 |
x_coordinate3 y_coordinate3 | #coordinate of a point which is on island3 |
x_coordinate4 y_coordinate4 | #coordinate of a point which is on island4 |
x_coordinate5 y_coordinate5 | #coordinate of a point which is on island5 |
Remarks
- There will be at most 100 islands.
- You can allocate only one array.(create an array for the terrain data).
- You cannot declare any other array in your program.
- You cannot use dynamic allocation.
- Do not submit your code without testing it with several different scenarios.
- Write comments in your code.
- Do not print anything to stdout and stderr.
- Do not submit any of the files you used for testing.
- Do not submit your output file.
Turn in:
- Source code of a complete C program. Name of the file should be in this format: <full_name>_<id>.c.
- Example: gokhan_kaya_000000.c. Please do not use any Turkish special characters.
- You don’t need to use an IDE for this assignment. Your code will be compiled and run in a command window.
- Your code will be compiled and tested on a Linux machine(Ubuntu). GCC will be used.
- Make sure you don’t get compile errors when you issue this command : gcc <full_name>_<id>.c.
- A script will be used in order to check the correctness of your results. So, be careful not to violate the expected output format.
- Provide comments unless you are not interested in partial credit. (If I cannot easily understand your design, you may loose points.)
You may not get full credit if your implementation contradicts with the statements in this document.