codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

359A.md (2673B)


      1 Source: https://codeforces.com/problemset/problem/359/A
      2 
      3 A. Table
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Simon has a rectangular table consisting of *n* rows and *m* columns. Simon numbered the rows of the table from top to bottom starting from one and the columns — from left to right starting from one. We'll represent the cell on the *x*-th row and the *y*-th column as a pair of numbers (*x*, *y*). The table corners are cells: (1, 1), (*n*, 1), (1, *m*), (*n*, *m*).
     22 
     23 Simon thinks that some cells in this table are good. Besides, it's known that no good cell is the corner of the table.
     24 
     25 Initially, all cells of the table are colorless. Simon wants to color all cells of his table. In one move, he can choose any good cell of table (*x*1, *y*1), an arbitrary corner of the table (*x*2, *y*2) and color all cells of the table (*p*, *q*), which meet both inequations: *min*(*x*1, *x*2) ≤ *p* ≤ *max*(*x*1, *x*2), *min*(*y*1, *y*2) ≤ *q* ≤ *max*(*y*1, *y*2).
     26 
     27 Help Simon! Find the minimum number of operations needed to color all cells of the table. Note that you can color one cell multiple times.
     28 
     29 Input
     30 
     31 The first line contains exactly two integers *n*, *m* (3 ≤ *n*, *m* ≤ 50).
     32 
     33 Next *n* lines contain the description of the table cells. Specifically, the *i*-th line contains *m* space-separated integers *a**i*1, *a**i*2, ..., *a**im*. If *a**ij* equals zero, then cell (*i*, *j*) isn't good. Otherwise *a**ij* equals one. It is guaranteed that at least one cell is good. It is guaranteed that no good cell is a corner.
     34 
     35 Output
     36 
     37 Print a single number — the minimum number of operations Simon needs to carry out his idea.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 3  
     45 0 0 0  
     46 0 1 0  
     47 0 0 0
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 4
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4 3  
     60 0 0 0  
     61 0 0 1  
     62 1 0 0  
     63 0 0 0
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 2
     70 ```
     71 
     72 Note
     73 
     74 In the first sample, the sequence of operations can be like this:
     75 
     76  ![](https://espresso.codeforces.com/565fd475c8e83b0fe7a3c841173a550c7a5198e5.png) 
     77 
     78 * For the first time you need to choose cell (2, 2) and corner (1, 1).
     79 * For the second time you need to choose cell (2, 2) and corner (3, 3).
     80 * For the third time you need to choose cell (2, 2) and corner (3, 1).
     81 * For the fourth time you need to choose cell (2, 2) and corner (1, 3).
     82 
     83 In the second sample the sequence of operations can be like this:
     84 
     85  ![](https://espresso.codeforces.com/58065713b01f09623e3d995baf698ff251d0f2ad.png) 
     86 
     87 * For the first time you need to choose cell (3, 1) and corner (4, 3).
     88 * For the second time you need to choose cell (2, 3) and corner (1, 1).