시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB60241653115026.932%

문제

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

예제 입력 1

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

예제 출력 1

5

힌트

(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으므로, (2, 3)위치에 있는 스위치는 누를 수 없다. 그러므로 불을 밝힐 수 있는 방의 최대 개수는 5이다.

W3sicHJvYmxlbV9pZCI6IjExOTY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZDg4XHVjZjFjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1Y2Q1Y1x1YWRmY1x1YzVkMCBOICZ0aW1lczsgTlx1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWM3MFx1YjMwMFx1ZDU1YyBcdWQ1ZGJcdWFjMDRcdWM3NDQgXHVjMGM4XHViODVjIFx1YzljMFx1YzVjOFx1YjJlNC4gXHVhYzAxIFx1YmMyOVx1Yzc0MCAoMSwgMSlcdWJkODBcdWQxMzAgKE4sTilcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNCgyICZsZTsgTiAmbGU7IDEwMCkuIFx1YzViNFx1YjQ2MFx1Yzc0NCBcdWJiMzRcdWMxMWNcdWM2Y2NcdWQ1NThcdWIyOTQgXHVjNTU0XHVjMThjIFx1YmNhMFx1YzJkY1x1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YmMyOVx1YzVkMCBcdWJkODhcdWM3NDQgXHViYzFkXHVkNzg4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2EwXHVjMmRjXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWJkODhcdWM3NzQgXHVjZjFjXHVjODM4XHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc3OCAoMSwgMSlcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHViYzI5XHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHViMmVjXHViODI0XHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSwgMSlcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyAoMSwgMilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViY2EwXHVjMmRjXHViMjk0IFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzNjXHViODVjXHViOWNjIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViYzI5XHVjNWQwXHVjMTFjXHViMjk0IFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMFx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViYzI5XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiA8XC9wPlxyXG5cclxuPHA+XHViY2EwXHVjMmRjXHVhYzAwIFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDIgJmxlOyBOICZsZTsgMTAwKVx1YWNmYywgTSgxICZsZTsgTSAmbGU7IDIwLDAwMClcdWM3NzQgXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggeCwgeSwgYSwgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICh4LCB5KVx1YmMyOVx1YzVkMFx1YzExYyAoYSwgYilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1Y2YxY1x1YWNlMCBcdWIwNGMgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWJjMjlcdWM1ZDAgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWM4NzBcdWM4MDhcdWQ1NThcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YzVlZFx1YzJkYyBcdWM1ZWNcdWI3ZWNcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmNhMFx1YzJkY1x1YWMwMCBcdWJkODhcdWM3NDQgXHVjZjI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4oMSwgMSlcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyAoMSwgMilcdWJjMjlcdWFjZmMgKDEsIDMpXHViYzI5XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwICgxLCAzKVx1YzczY1x1Yjg1YyBcdWFjNzhcdWM1YjRcdWFjMDBcdWMxMWMgKDIsIDEpXHViYzI5XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKDIsIDEpXHViYzI5XHVjNWQwXHVjMTFjXHViMjk0IFx1YjJlNFx1YzJkYyAoMiwgMilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1Y2YyNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMiwgMylcdWJjMjlcdWM3NDAgXHVjNWI0XHViNDUwXHVjNmNjXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYmMwXHViODVjLCAoMiwgMylcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyMDRcdWI5N2MgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViN2VjXHViYmMwXHViODVjIFx1YmQ4OFx1Yzc0NCBcdWJjMWRcdWQ3OTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YjI5NCA1XHVjNzc0XHViMmU0LiA8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExOTY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3dpdGNoaW5nIG9uIHRoZSBMaWdodHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyByZWNlbnRseSBidWlsdCBhbiBlbm9ybW91cyBiYXJuIGNvbnNpc3Rpbmcgb2YgYW4gXFwoTiBcXHRpbWVzIE5cXCkgZ3JpZCBvZiByb29tcyAoXFwoMiBcXGxlcSBOIFxcbGVxIDEwMFxcKSksIG51bWJlcmVkIGZyb20gXFwoKDEsMSlcXCkgdXAgdG8gXFwoKE4sTilcXCkuIEJlaW5nIHNvbWV3aGF0IGFmcmFpZCBvZiB0aGUgZGFyaywgQmVzc2llIHRoZSBjb3cgd2FudHMgdG8gdHVybiBvbiB0aGUgbGlnaHRzIGluIGFzIG1hbnkgcm9vbXMgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkJlc3NpZSBzdGFydHMgaW4gcm9vbSBcXCgoMSwxKVxcKSwgdGhlIG9ubHkgcm9vbSB0aGF0IGlzIGluaXRpYWxseSBsaXQuIEluIHNvbWUgcm9vbXMsIHNoZSB3aWxsIGZpbmQgbGlnaHQgc3dpdGNoZXMgdGhhdCBzaGUgY2FuIHVzZSB0byB0b2dnbGUgdGhlIGxpZ2h0cyBpbiBvdGhlciByb29tczsgZm9yIGV4YW1wbGUgdGhlcmUgbWlnaHQgYmUgYSBzd2l0Y2ggaW4gcm9vbSBcXCgoMSwxKVxcKSB0aGF0IHRvZ2dsZXMgdGhlIGxpZ2h0cyBpbiByb29tIFxcKCgxLDIpXFwpLiBCZXNzaWUgY2FuIG9ubHkgdHJhdmVsIHRocm91Z2ggbGl0IHJvb21zLCBhbmQgc2hlIGNhbiBvbmx5IG1vdmUgZnJvbSBhIHJvb20gXFwoKHgseSlcXCkgdG8gaXRzIGZvdXIgYWRqYWNlbnQgbmVpZ2hib3JzIFxcKCh4LTEseSlcXCksIFxcKCh4KzEseSlcXCksIFxcKCh4LHktMSlcXCkgYW5kIFxcKCh4LHkrMSlcXCkgKG9yIHBvc3NpYmx5IGZld2VyIG5laWdoYm9ycyBpZiB0aGlzIHJvb20gaXMgb24gdGhlIGJvdW5kYXJ5IG9mIHRoZSBncmlkKS48XC9wPlxyXG5cclxuPHA+UGxlYXNlIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2Ygcm9vbXMgQmVzc2llIGNhbiBpbGx1bWluYXRlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgaW50ZWdlcnMgXFwoTlxcKSBhbmQgXFwoTVxcKSAoXFwoMSBcXGxlcSBNIFxcbGVxIDIwLDAwMFxcKSkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IFxcKE1cXCkgbGluZXMgZWFjaCBkZXNjcmliZSBhIHNpbmdsZSBsaWdodCBzd2l0Y2ggd2l0aCBmb3VyIGludGVnZXJzIFxcKHhcXCksIFxcKHlcXCksIFxcKGFcXCksIFxcKGJcXCksIHRoYXQgYSBzd2l0Y2ggaW4gcm9vbSBcXCgoeCx5KVxcKSBjYW4gYmUgdXNlZCB0byB0b2dnbGUgdGhlIGxpZ2h0cyBpbiByb29tIFxcKChhLGIpXFwpLiBNdWx0aXBsZSBzd2l0Y2hlcyBtYXkgZXhpc3QgaW4gYW55IHJvb20sIGFuZCBtdWx0aXBsZSBzd2l0Y2hlcyBtYXkgdG9nZ2xlIHRoZSBsaWdodHMgb2YgYW55IHJvb20uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSBnaXZpbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvb21zIEJlc3NpZSBjYW4gaWxsdW1pbmF0ZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SGVyZSwgQmVzc2llIGNhbiB1c2UgdGhlIHN3aXRjaCBpbiBcXCgoMSwxKVxcKSB0byB0dXJuIG9uIGxpZ2h0cyBpbiBcXCgoMSwyKVxcKSZuYnNwO2FuZCBcXCgoMSwzKVxcKS4gU2hlIGNhbiB0aGVuIHdhbGsgdG8gXFwoKDEsMylcXCkgYW5kIHR1cm4gb24gdGhlIGxpZ2h0cyBpbiBcXCgoMiwxKVxcKSwgZnJvbSB3aGljaCBzaGUgY2FuIHR1cm4gb24gdGhlIGxpZ2h0cyBpbiBcXCgoMiwyKVxcKS4gVGhlIHN3aXRjaCBpbiBcXCgoMiwzKVxcKSBpcyBpbmFjY2Vzc2libGUgdG8gaGVyLCBiZWluZyBpbiBhbiB1bmxpdCByb29tLiBTaGUgY2FuIHRoZXJlZm9yZSBpbGx1bWluYXRlIGF0IG1vc3QgNSByb29tcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2015-2016 Season > USACO December 2015 Contest > Silver 1번