Data Structure讲解、BFS留学生辅导、Python/c++，Java语言讲解 讲解Java程序|辅导Python程序
- 首页 >> 其他 Data Structure Assignment # 2
2019-04-11 Prof. Joonwon Lee
BFS(Breadth-First Search)
–Routing from the root node (the start node) to the nearest node first, and later to the far node
–You should visit all nodes once
–Use queue data structure which can retrieve the visited nodes in order. (FIFO)
–You have to use BFS to solve this assignment.
Solve a problem: Queue
–Hyeonah's tomato farm has a large warehouse for storing tomatoes
–The tomatoes are placed in a box (a grid-shaped box) as shown in the picture below and stored in a warehouse
–Some of the tomatoes stored in the warehouse are ripe, but some are unripe.
–After a day of storage, unripe tomatoes will ripe if its neighbors contain of ripe tomatoes.
–The neighbors of one tomato are the tomatoes in the left, right, front, or back.
–Assume there is no effect to tomatoes in the diagonal direction and assumes that the tomatoes do not ripen by themselves.
–When storing the tomatoes at her warehouse, Hyeonah wants to know what is the minimum number of days that all of the tomatoes will ripe.
–Given the size of the grid-shaped box that is used to store the tomatoes in the warehouse, and the information of ripe tomatoes and unripe tomatoes, write a program to get the minimum number of days that all of the tomatoes will ripen a few days.
–However, note that some boxes may not contain tomatoes
–Set one of the tomatoes as the root node (start node) and then use BFS
to solve the problem
Examples of Input
–In the first line, enter the number of test cases.
–The second line contains two integers, M and N, indicating the size of the grid-shaped box.
–M is the horizontal size, and N is the vertical size of the grid-shaped box.
–Conditionally, 2 ≤ M, N ≤ 1,000.
–The third line contains information about the tomatoes stored in a box. The input will be a matrix with size M x N.
–In the matrix, an integer 1 represents a ripe tomato, an integer 0 represents unripe tomatoes, and an integer -1 represents a space containing no tomato.
–You should print the minimum days until the tomatoes are all ripe
Examples of Ouput
–If all the tomatoes have been ripen from the time they are stored, 0 should be the output.
–If the all tomatoes are not ripe, they should be printed as -1.
Examples of Input & Ouput
2019-04-11 Prof. Joonwon Lee
BFS(Breadth-First Search)
–Routing from the root node (the start node) to the nearest node first, and later to the far node
–You should visit all nodes once
–Use queue data structure which can retrieve the visited nodes in order. (FIFO)
–You have to use BFS to solve this assignment.
Solve a problem: Queue
–Hyeonah's tomato farm has a large warehouse for storing tomatoes
–The tomatoes are placed in a box (a grid-shaped box) as shown in the picture below and stored in a warehouse
–Some of the tomatoes stored in the warehouse are ripe, but some are unripe.
–After a day of storage, unripe tomatoes will ripe if its neighbors contain of ripe tomatoes.
–The neighbors of one tomato are the tomatoes in the left, right, front, or back.
–Assume there is no effect to tomatoes in the diagonal direction and assumes that the tomatoes do not ripen by themselves.
–When storing the tomatoes at her warehouse, Hyeonah wants to know what is the minimum number of days that all of the tomatoes will ripe.
–Given the size of the grid-shaped box that is used to store the tomatoes in the warehouse, and the information of ripe tomatoes and unripe tomatoes, write a program to get the minimum number of days that all of the tomatoes will ripen a few days.
–However, note that some boxes may not contain tomatoes
–Set one of the tomatoes as the root node (start node) and then use BFS
to solve the problem
Examples of Input
–In the first line, enter the number of test cases.
–The second line contains two integers, M and N, indicating the size of the grid-shaped box.
–M is the horizontal size, and N is the vertical size of the grid-shaped box.
–Conditionally, 2 ≤ M, N ≤ 1,000.
–The third line contains information about the tomatoes stored in a box. The input will be a matrix with size M x N.
–In the matrix, an integer 1 represents a ripe tomato, an integer 0 represents unripe tomatoes, and an integer -1 represents a space containing no tomato.
–You should print the minimum days until the tomatoes are all ripe
Examples of Ouput
–If all the tomatoes have been ripen from the time they are stored, 0 should be the output.
–If the all tomatoes are not ripe, they should be printed as -1.
Examples of Input & Ouput