Mr. Gorilla, a muscular man, has gotten lost in a maze. The maze is a rectangle of n rows and m columns, and it consists of open spaces and walls. Mr. Gorilla starts at positions and he wants to go to position G. Both s and G are open spaces. Mr. Gorilla can move in four directions, up, down, left, and right. The time it takes to move is determined in this way: If the position he's trying to move into is not a wall, it takes one second. If the position he's trying to move into is a wall, he breaks down the wall because he is so strong and moves into the new space that was occupied by the wall before he broke it down. However, each wall he breaks down makes him more tired, so he must rest r seconds after breaking down each wall, where z is the total number of walls he has broken down prior to that wall. Moreover, it takes one more second to actually move into the new space. Mr. Gorilla is not good at working with his brain. Therefore, implement a program which calculates for Mr. Gorilla the minimum amount of time needed for him to move from position s to position G. The mission You are given a maze. Calculate the minimum amount of time needed for Mr. Gorilla to move from position s to position G. Implementation CLI Implement a command line application that receives standard input and writes the answer to its standard output. For details, see the "Command line application template" section at the bottom of the page. Input rules Your CLI program should receive standard input. ./ myApp The format of the standard input is as below: n m S1 Sn The conditions are as follows: 2 s denotes the position Mr. Gorilla starts from 6 denotes the destination of Mr. Gorilla denotes an open space # denotes a wall s and G are always open spaces The following additional condition is satisfied for 30% of all test cases. There are no walls # in the given maze Output rule Your CLI program should write the answer to its standard output. The format of the standard output is as below: Standard output answer On the 1st line, print the minimum time needed for Mr. Gorilla to move from position s to position G. Input & Output examples Example 1 Standard input ( 00_samplel.in ) 3 3 S## #. G Standard output 5 Let's call the position of the ith row and the jth column the point (i, j) (1 He reaches his destination. Example 2 Standard Input ( 00_sample2.in ) 3 3 S## ### .. G Standard Output 4 Mr. Gorilla starts at point (1, 1). He breaks down the wall at point (2, 1) and moves into the space. As he has broken no walls previously to this wall, it takes 0 seconds to break this wall. It takes 1 second to move. He moves to point (3, 1). It takes 1 second. He moves to point (3, 2). It takes 1 second. He moves to point (3, 3). It takes 1 second. He reaches his destination. Example 3 Standard Input ( 00_sample3.in ) 5 3 ... ..S ... .G. ... Standard Output 3 This test case satisfies the conditions of the simple test cases because the maze has no walls. Mr. Gorilla starts at point (2, 3). He moves to point (2, 2). This takes 1 second. He moves to point (3, 2). This takes 1 second. He moves to point (4, 2). This takes 1 second. He reaches his destination. There are other input & output examples defined in this file: test/basic_testcases.json You can use it as a reference while working on this exercise. Command line application template for C Implement CLI application by editing main.c. You may add new files to keep your code clean, if it is allowed in your challenge. How to get stdin lines You can use scanf, fget , etc. The template has sample code which using fget. You can modify that code as you like. How to output result How to output result You can use printf. printf ("argv[i]: %s ", i, argv[i]); How to compile To compile, we are using clang gcc command. If you want to change compile option or etc, please edit makefile.