| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Winter's Coming
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1114 Accepted Submission(s): 86
Problem Description
¡åYou are too young to be burdened with all my cares,¡å the father told her, ¡åbut you are also a Stark of Winterfell. You know our words.¡å
¡åWinter is coming,¡å Arya whispered, thinking of Nymeria. She hugged her knees against her chest, suddenly afraid.
¡åRemember the sigil of our House, Arya. Let me tell you something about it. When the snows fall and the white winds blow, the lone Wolf dies, but the pack survives. Summer is the time for squabbles. In winter, we must protect one another, keep each other warm, share our strengths. So if you must hate, Arya, hate those who would truly do us harm. Sansa... Sansa is your sister. You may be as different as the sun and the moon, but the same blood flows through both your hearts. You need her, as she needs you... and I need both of you, gods help me. Gods commanded us to build a long wall, which is regardless of the thickness, to defend the attack from the Lannister. Now we should carry out the wall.¡å Ned Stark sounded so tired that it made Arya sad.
¡åI do not mean to frighten you, but neither will I lie to you. We have come to a dark dangerous place, child. We have enemies who mean us ill in the King's Landing. We'll point the swords to the Lannister, rather than fight a war among ourselves. Our construction crew will build a wall which connect the north border and south border, separate the mainland into exact two parts. All our Wolf's cities should lie on the left part, while All Lannister's cities lie on the right part. Precisely, the wall can't pass through a grid more than once, and should run parallel or vertically to the four borders. With winter soon upon us, that is a different matter that we should minimize the time cost.¡å
¡åHow much time do we have, roughly?¡å Arya take out the draft and has been ready to calculate.
¡åWinter is coming.¡å Her father frowned.
¡åWinter is coming,¡å Arya whispered, thinking of Nymeria. She hugged her knees against her chest, suddenly afraid.
¡åRemember the sigil of our House, Arya. Let me tell you something about it. When the snows fall and the white winds blow, the lone Wolf dies, but the pack survives. Summer is the time for squabbles. In winter, we must protect one another, keep each other warm, share our strengths. So if you must hate, Arya, hate those who would truly do us harm. Sansa... Sansa is your sister. You may be as different as the sun and the moon, but the same blood flows through both your hearts. You need her, as she needs you... and I need both of you, gods help me. Gods commanded us to build a long wall, which is regardless of the thickness, to defend the attack from the Lannister. Now we should carry out the wall.¡å Ned Stark sounded so tired that it made Arya sad.
¡åI do not mean to frighten you, but neither will I lie to you. We have come to a dark dangerous place, child. We have enemies who mean us ill in the King's Landing. We'll point the swords to the Lannister, rather than fight a war among ourselves. Our construction crew will build a wall which connect the north border and south border, separate the mainland into exact two parts. All our Wolf's cities should lie on the left part, while All Lannister's cities lie on the right part. Precisely, the wall can't pass through a grid more than once, and should run parallel or vertically to the four borders. With winter soon upon us, that is a different matter that we should minimize the time cost.¡å
¡åHow much time do we have, roughly?¡å Arya take out the draft and has been ready to calculate.
¡åWinter is coming.¡å Her father frowned.
Input
There are multiple cases. The first line of each case contains two integers, N, M (1 ¡Ü N ¡Ü 20, 1 ¡Ü M ¡Ü 10), indicating the width and length of the mainland's layout.
In the map, the character is 'W' indicated the Wolf's city, 'L' indicated the Lannister's city, '#' means a grid where forbade any construction, and a number in '0'-'9' indicated the time cost to build a wall on this grid.
In the map, the character is 'W' indicated the Wolf's city, 'L' indicated the Lannister's city, '#' means a grid where forbade any construction, and a number in '0'-'9' indicated the time cost to build a wall on this grid.
Output
For each case, output one integer, the minimum time cost to build a valid wall, or -1 if we can't work out an approach.
Sample Input
6 8 88W888L8 888#W888 888888L8 8W88L#88 8888888L 88888W88
Sample Output
88
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-04-20 15:09:04, Gzip enabled |
Administration |