Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NHPAINT - Naruto học máy tính

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nhpaint


Hôm nay, Naruto bắt đầu làm quen với máy tính. Chương trình đầu tiên mà cậu được học là paint :D . Và tất nhiên,đã học là phải có bài tập về nhà, Naruto được giao cho 1 bức tranh đen trắng. Bức tranh là 1 hình chữ nhật m dòng n cột, mỗi một ô chỉ tô 1 trong 2 màu: đen hoặc trắng. Nhiệm vụ của Naruto là phải vẽ lại giống y hệt bức tranh này trên paint !!!

Nhưng với tính nghịch ngợm của mình, Naruto nào có chịu ngồi im trong lớp nghe giảng nên cậu chẳng biết phải làm thế nào để thực hành bài tập về nhà cả. Không muốn bị thầy giáo phạt, cậu đành phải làm bài tập theo một cách rất chi là thủ công như sau : phóng to trang giấy vẽ lên cho đến khi có thể nhìn thấy từng điểm ảnh, rồi sau đo chép lại bức tranh bằng cách tô đen hoặc tô trắng từng điểm ảnh một !!! Và để tránh nhầm lẫn, Naruto sẽ chép lại từng cột một. Đầu tiên, Naruto sẽ chọn trên trang vẽ một cột i bất kì, so sánh sang cột i ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình. Sau khi tô xong cột đầu tiên này, từ lần thứ 2 trở đi, Naruto sẽ vẽ tiếp theo quy tắc sau

- Chọn 1 cột j bất kì chưa từng được chon trước đó, copy nguyên cột i vừa vẽ lên cột j rồi so sánh sang cột j ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình

- Chọn cột j chưa từng được chọn trước đó,j là một trong 2 cột ở cạnh cột vừa tô (j=i+1 hoặc j=i-1), so sánh cột j với cột tương ứng ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình

Trang vẽ ban đầu toàn là màu trắng. Thời gian để chỉnh sửa lại 1 điểm ảnh là 1s, thời gian để copy 1 cột và paste vào 1 cột khác là không đáng kể. Bạn hãy giúp Naruto tính xem cậu ta sẽ phải mất ít nhất bao nhiêu lâu để hoàn thành bài tập của mình.

Input

Dòng đầu là 2 số m,n (m<10001, n<16) - độ lớn của bức tranh mẫu

m dòng sau thể hiện bức tranh mẫu, mỗi dòng là 1 dãy gồm n phần tử mang 1 trong 2 giá trị: 0 hoặc 1, 0 thể hiện cho màu trắng và ngược lại.

Output

Ghi ra thời gian ngắn nhất Naruto hoàn thành bài tập của mình

Example

Input:
3 4
0000
0110
0000

Output:
1

Giải thích test đề bài: đầu tiên Naruto se chọn tô cột 1,thời gian để tô xong cột 1 la 0s, copy cột 1 sang cột 4,chỉnh sửa lại mất 0s,chuyển sang tô cột 3 bên cạnh hết 1s, copy cột 3 paste lên cột 2.Vậy Naruto hết 1s để hoàn thành bức tranh


Được gửi lên bởi:Del nick !!!
Ngày:2009-03-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 ERL GOSU JS-RHINO NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET

hide comments
2017-04-02 11:31:31
em làm giống bài LEM3 mà cứ bị WA quài :((
2016-12-04 05:49:59
hoLdTT\moc.enoedi
2016-08-27 21:12:17 even when you try to hurt me...
ai giải thích lại đề bài với... em cảm thấy bối rối....
2016-08-09 08:50:30
sao Naruto không copy cả bức tranh mẫu mà phải vẽ lại từng cột cho mệt nhỉ =)))
2011-04-26 01:49:02 Bống
đề nói ko rõ tí nào, làm mình tưởng thuật toán sai, ai ngờ hiểu đề sai
2011-01-23 04:13:28 ðẹp trai bẩm sinh
Bài này mình xây dựng đồ thị rồi làm như bài LEM3 :D
2010-05-27 17:21:35 ntt
he he, lay bai wrong answer cach day dung 1 nam submit thi lai accept

Last edit: 2010-05-27 17:23:13
2009-05-21 22:27:41 ntt
Ban giai thich de bai ro hon va co the add them vai test nua duoc ko?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.