Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.2 kB
2
Indexable
Never
Laughing Bomb
You are busy to promote a newly released film in a movie theater. The title is ‘Biochemical Laughing Bomb’ which is about terror.
Guerrillas drop a biochemical laughing bomb in the middle of a city. Once exposed, you have to laugh all your life. The bomb will contaminate four people around it during 1 second, and another four around each of them during another one second. However, you won’t be contaminated if you are not in the adjacent four directions. as the below shows the location of the bomb and affected people, and shows contamination process in seconds and you can figure out that the whole city is contaminated in 8 seconds.
In order to protect the city from the epidemic, create a program that figures out when the city will be contaminated by the bomb for the last.
             
Time limit: 1 second (java: 2 seconds)

[Input]
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row.
The row and column of the city, N and M are given by being separated with a blank on the first row of each test case. (1 ≤ N, M ≤ 100)
The status within city is given by being separated with a blank from the second row to N number rows. 1 means people exist and 0 means people do not exist. 
The coordinate of the row and column on which the bomb fall is given by being separated with a blank on the last row. 

[Output]
Output how long does it take to contaminate al people on the first row of each test case. 

[I/O Example] 
Input 
2
7 8
0 0 1 1 0 0 0
1 1 1 1 0 1 0
0 0 1 1 1 1 1
0 1 1 1 1 1 1
0 1 0 0 1 1 0
0 1 1 1 1 0 0
0 0 1 0 1 1 1
0 0 0 0 1 0 0
2 5
10 10
1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 1 0 1 1 0
0 0 1 1 0 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 1 0 1 0 1 1 1 1 0
0 0 0 0 0 1 1 0 0 0
1 0 1 0 1 0 1 1 0 0
0 0 1 1 1 1 1 1 1 1
1 0 1 0 0 1 0 1 1 0
1 1 1 0 0 0 0 1 1 1
2 2

Output
8
21


#include <stdio.h>
#define MAX_SIZE 101
int citymap[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int Answer;
int row_size = 0;
int col_size = 0;
int bomb_row, bomb_col;

void traverse(int row, int col, int cur_value)
{
    //check booundary condition
    if ((row < 1) || (row > row_size) || (col < 1) || (col > col_size))
        return;

    //check for data-retrun condition in the map
    if (citymap[row][col] == 0)
        return;
    //depth check
    
    //check for visited or anyother condition given additionally like compatibilit of traversal etc
    if (visited[row][col])
    {
        if(citymap[row][col] > cur_value)
        {
            citymap[row][col] = cur_value;
        }
        else
        {
            return;
        }
    }
    else
    { //if not returning , execute steps at this level
        visited[row][col] = 1;
        citymap[row][col] = cur_value;
    }

    //traverse forward once done with this level
    traverse(row, col+1, cur_value + 1);
    traverse(row+1, col, cur_value + 1);
    traverse(row, col-1, cur_value + 1);
    traverse(row-1, col, cur_value + 1);

    return;
}

int main(void)
{
    int tc, T;

    int i, j;


    // The freopen function below opens input.txt file in read only mode, and afterward,
    // the program will read from input.txt file instead of standard(keyboard) input.
    // To test your program, you may save input data in input.txt file,
    // and use freopen function to read from the file when using scanf function.
    // You may remove the comment symbols(//) in the below statement and use it.
    // But before submission, you must remove the freopen function or rewrite comment symbols(//).

     //freopen("sample_input_laughingbomb_debug.txt", "r", stdin);

    // If you remove the statement below, your program's output may not be rocorded
    // when your program is terminated after the time limit.
    // For safety, please use setbuf(stdout, NULL); statement.

    setbuf(stdout, NULL);

    scanf("%d", &T);
    for (tc = 0; tc < T; tc++)
    {
        //reset all varaiables
        row_size = 0;
        col_size = 0;

        bomb_row = 0;
        bomb_col = 0;

        for (i = 0; i < MAX_SIZE; i++)
        {
            for (j = 0; j < MAX_SIZE; j++)
            {
                citymap[i][j] = 0;
                visited[i][j] = 0;
            }
        }

        Answer = 0;

        scanf("%d", &col_size);
        scanf("%d", &row_size);


        for (i = 1; i <= row_size; i++)
        {
            for (j = 1; j <= col_size; j++)
            {
                scanf("%d", &citymap[i][j]);
            }
        }

        scanf("%d %d", &bomb_col, &bomb_row);
        citymap[bomb_row][bomb_col] = 1;
        traverse(bomb_row, bomb_col,1);
        

        
        for (i = 1; i <= row_size; i++)
        {
            for (j = 1; j <= col_size; j++)
            {
                if (Answer < citymap[i][j])
                    Answer = citymap[i][j];
            }
            
        }

        printf("%d \n", Answer);
    }

    return 0;//Your program should return 0 on normal termination.
}