Chatbox

Các bạn vui lòng dùng từ ngữ lịch sự và có văn hóa,sử dụng Tiếng Việt có dấu chuẩn. Chúc các bạn vui vẻ!
02/11/2013 17:11 # 1
vnttqb
Cấp độ: 13 - Kỹ năng: 8

Kinh nghiệm: 5/130 (4%)
Kĩ năng: 39/80 (49%)
Ngày gia nhập: 21/03/2011
Bài gởi: 785
Được cảm ơn: 319
[codeforces] #209_div 2 - A. Table


A. Table
time limit per test
 1 second
memory limit per test
 256 megabytes
input
 standard input
output
 standard output

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).

Simon thinks that some cells in this table are good. Besides, it's known that no good cell is the corner of the table.

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(x1, y1), an arbitrary corner of the table (x2, y2) and color all cells of the table (p, q), which meet both inequations: min(x1, x2) ≤ p ≤ max(x1, x2)min(y1, y2) ≤ q ≤ max(y1, y2).

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.

Input

The first line contains exactly two integers nm (3 ≤ n, m ≤ 50).

Next n lines contain the description of the table cells. Specifically, the i-th line contains m space-separated integers ai1, ai2, ..., aim. Ifaij equals zero, then cell (i, j) isn't good. Otherwise aij equals one. It is guaranteed that at least one cell is good. It is guaranteed that no good cell is a corner.

Output

Print a single number — the minimum number of operations Simon needs to carry out his idea.

Sample test(s)
input
3 3
0 0 0
0 1 0
0 0 0
output
4
input
4 3
0 0 0
0 0 1
1 0 0
0 0 0
output
2
Note

In the first sample, the sequence of operations can be like this:

 

 

 

  • For the first time you need to choose cell (2, 2) and corner (1, 1).
  • For the second time you need to choose cell (2, 2) and corner (3, 3).
  • For the third time you need to choose cell (2, 2) and corner (3, 1).
  • For the fourth time you need to choose cell (2, 2) and corner (1, 3).

 

In the second sample the sequence of operations can be like this:

 

 
  • For the first time you need to choose cell (3, 1) and corner (4, 3).
  • For the second time you need to choose cell (2, 3) and corner (1, 1).

 

____________________________________________________________________________________
 
#include <iostream>
using namespace std;
int n,m;
int a[55][55];
void Read()
{
cin>>n>>m;
for ( int i = 1;i<=n; i++)
for ( int j = 1; j<= m ; j++)
cin>>a[i][j];
}
void Process()
{
if (a[1][m] + a[n][m] + a[n][1] + a[1][1] >=1 )
{
cout<<"1";
return;
}
for ( int i = 1; i<= m; i++)
if (a[1][i] == 1)
{
cout<<"2";
return;
}
for ( int i = 1; i<= m; i++)
if (a[n][i] == 1)
{
cout<<"2";
return;
}
for ( int i = 1; i<= n; i++)
if (a[i][1] == 1)
{
cout<<"2";
return;
}
for ( int i = 1; i<= n; i++)
if (a[i][m] == 1)
{
cout<<"2";
return;
}
for ( int i = 2;i<n; i++)
for ( int j = 2; j< m ; j++)
if (a[i][j]== 1 ) 
{
cout<<"4";
return;
}
 
}
int main()
{
Read();
Process();
}
 

 



======================================================================================================

Cuộc đời là một dòng sông. Ai không bơi thì chết. 
 

Name: Tien (Tory) TRAN
Email: TranTien29@gmail.com


 
Copyright© Đại học Duy Tân 2010 - 2019