시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1511 1053 895 71.888%

문제

m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.

그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.

박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.

출력

각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.

예제 입력 1

3
5 4
1 0 0 0
0 0 1 0
1 0 0 1
0 1 0 0
1 0 1 0
3 3
1 1 1
1 1 1
0 0 0
5 6
1 0 1 1 0 1
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 1 0 1 0 1

예제 출력 1

8
6
16
W3sicHJvYmxlbV9pZCI6Ijk0NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPm1cdWQ1ODkgblx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZGY4XHViOWFjXHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzdjXHViZDgwIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWJjMTVcdWMyYTRcdWFjMDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVjNTQ0XHViNzk4XHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNFx1YmE3NCwgXHViYzE1XHVjMmE0XHViMjk0IFx1YzMxM1x1YzVlY1x1YzljNCBcdWMwYzFcdWQwZGNcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YmMgKGEpXHVjNzU4IFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgNVx1ZDU4OSA0XHVjNWY0XHVjNzc0XHVhY2UwLCA3XHVjZTc4XHVjNWQwXHViMjk0IFx1YmMxNVx1YzJhNFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQsIFx1YWRmOFx1YjliYyAoYilcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYm94LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3MXB4OyB3aWR0aDoyOTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJjMTVcdWMyYTRcdWFjMDAgXHVjNmMwXHVjOWMxXHVjNzc4IFx1YWM3MFx1YjlhY1x1YjI5NCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHVjMzEzXHVjNzc0XHVhZTMwIFx1YzgwNCBcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTVjIFx1Y2U3OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjllOCBcdWM2N2NcdWNhYmQgXHVjNWY0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM2YzBcdWM5YzFcdWM3NzggXHVhYzcwXHViOWFjXHViMjk0IDJcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YWM3MFx1YjlhYyAoXHVhYzAxIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OSkgXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3MDRcdWM3NTggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YmMxNVx1YzJhNCA3XHVhYzFjXHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWFjNzBcdWI5YWNcdWIyOTQgOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgbVx1YWNmYyBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBtLCBuICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1YWMwMSBcdWQ1ODlcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YjRkYyBcdWNjYWIgXHVkNTg5XHViZDgwXHVkMTMwIFx1YjljOFx1YzljMFx1YjljOSBcdWQ1ODlcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYzE1XHVjMmE0XHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDAgMVx1Yjg1YywgXHViMmU0XHViOTc4IFx1Y2U3OFx1Yzc0MCAwXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzIxOCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NDU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm94ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ3JpZCB3aXRoIG0gcm93cyBhbmQgbiBjb2x1bW5zIGlzIGdpdmVuLiBTb21lIGNlbGxzIG9mIHRoZSBncmlkIGFyZSBvY2N1cGllZCBieSBib3hlcy4gSWYgYWxsIHRoZSBib3hlcyBvZiB0aGUgZ3JpZCBtb3ZlIGRvd253YXJkcyB1bnRpbCB0aGV5IGNhbm5vdCBtb3ZlIGFueSBmdXJ0aGVyLCB0aGUgYm94ZXMgd2lsbCBiZSBzdGFja2VkIGF0IHRoZSBib3R0b20gb2YgdGhlIGdyaWQuIEFuIGV4YW1wbGUgaXMgc2hvd24gaW4gRmlndXJlIDEuIEluIEZpZ3VyZSAxKGEpLCB0aGVyZSBpcyBhIGdyaWQgd2l0aCA1IHJvd3MgYW5kIDQgY29sdW1ucywgYW5kIDcgY2VsbHMgYXJlIG9jY3VwaWVkIGJ5IGJveGVzLiBBZnRlciBtb3ZpbmcgZXZlcnkgYm94IGRvd253YXJkcyBhcyBtdWNoIGFzIHBvc3NpYmxlLCB0aGUgYm94ZXMgYXJlIHN0YWNrZWQgYXQgdGhlIGJvdHRvbSBvZiB0aGUgZ3JpZCBhcyBzaG93biBpbiBGaWd1cmUgMShiKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ib3gucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTcxcHg7IHdpZHRoOjI5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBBIGdyaWQgd2l0aCA3IGJveGVzPFwvcD5cclxuXHJcbjxwPlRoZSBtb3ZpbmcgZGlzdGFuY2Ugb2YgYSBib3ggaXMgZGVmaW5lZCB0byBiZSB0aGUgZGlzdGFuY2UgdGhlIGJveCBoYXMgdHJhdmVsZWQgdW50aWwgYWxsIHRoZSBib3hlcyBhcmUgc3RhY2tlZCBhdCB0aGUgYm90dG9tIG9mIHRoZSBncmlkLiBGb3IgZXhhbXBsZSwgdGhlIG1vdmluZyBkaXN0YW5jZSBvZiB0aGUgaGlnaGVzdCBib3ggYXQgdGhlIGxlZnRtb3N0IGNvbHVtbiBpcyAyLiBJbiB0aGlzIHByb2JsZW0sIHdlIGFyZSBpbnRlcmVzdGVkIGluIHRoZSB0b3RhbCBtb3ZpbmcgZGlzdGFuY2Ugb2YgYWxsIGJveGVzLCB0aGF0IGlzLCB0aGUgc3VtIG9mIHRoZSBtb3ZpbmcgZGlzdGFuY2VzIG9mIGFsbCBib3hlcy4gSW4gdGhlIGFib3ZlIGV4YW1wbGUsIHRoZSB0b3RhbCBtb3ZpbmcgZGlzdGFuY2Ugb2YgdGhlIDcgYm94ZXMgaXMgOC4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuWW91IGFyZSB0byBjYWxjdWxhdGUgdGhlIHRvdGFsIG1vdmluZyBkaXN0YW5jZSBvZiBib3hlcyBmb3IgYSBnaXZlbiBncmlkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIG0gYW5kIG4gKDEgJmxlOyBtLCBuICZsZTsgMTAwKSwgd2hlcmUgbSBpcyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIG4gaXMgdGhlIG51bWJlciBvZiBjb2x1bW5zIG9mIHRoZSBncmlkLiBJbiB0aGUgbmV4dCBtIGxpbmVzLCBlYWNoIGxpbmUgY29udGFpbnMgbiBpbnRlZ2VycyByZXByZXNlbnRpbmcgYSByb3cgb2YgdGhlIGdyaWQuIFRoZSBpbmZvcm1hdGlvbiBvZiBhIGdyaWQgaXMgZ2l2ZW4gZnJvbSB0b3Agcm93IHRvIGJvdHRvbSByb3cuIElmIGEgY2VsbCBpcyBvY2N1cGllZCBieSBhIGJveCwgaXQgaXMgcmVwcmVzZW50ZWQgYnkgdGhlIGludGVnZXIgMSwgb3RoZXJ3aXNlIGl0IGlzIHJlcHJlc2VudGVkIGJ5IHRoZSBpbnRlZ2VyIDAuIFRoZXJlIGlzIGEgc2luZ2xlIHNwYWNlIGJldHdlZW4gdHdvIGludGVnZXJzIGluIHRoZSBzYW1lIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSB0b3RhbCBtb3ZpbmcgZGlzdGFuY2Ugb2YgdGhlIGJveGVzIGZvciB0aGUgZ2l2ZW4gZ3JpZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2013 A번