wuli通通和doge
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 20 Accepted Submission(s) : 6
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有一天，wuli通通梦见了一个迷宫以及一只蠢萌的doge。迷宫是一个n行m列的网格，wuli通通把doge丢到迷宫中后，如果它所在的位置是空白，那么它会停在原地，如果它所在的位置有指引牌，那么它会沿着指引牌所指引的方向一直前进，直到遇到下一个指引牌，一旦遇到下一个指引牌，它会按照下一个指引牌所指引的方向一直前进，如此往复。现在wuli通通想要把这只doge困在迷宫中，也就是说，无论将它丢到迷宫的任意一个位置，它都不会走出迷宫。
如果doge已经在迷宫的上边界，仍然向上走，那么它会被认定为走出了迷宫，其他方向同理。
为了达成这个目的，wuli通通必须将迷宫中指引牌所指引的方向，那么问题来了，wuli通通至少修改几个指引牌的方向，才能达到目的。
如果doge已经在迷宫的上边界，仍然向上走，那么它会被认定为走出了迷宫，其他方向同理。
为了达成这个目的，wuli通通必须将迷宫中指引牌所指引的方向，那么问题来了，wuli通通至少修改几个指引牌的方向，才能达到目的。
Input
输入数据的第一行是一个正整数t，表示接下来有t组数据。
对于每组数据，第一行是两个正整数n,m，表示迷宫有n行m列(1<=n,m<=100)。
接下来n行，每行m个字符，描述迷宫——
"."(点)表示这个位置是空白，
"<"(小于)表示这个位置是向左的指引牌，
">"(大于)表示这个位置是向右的指引牌，
"^"(异或)表示这个位置是向上的指引牌，
"v"(字母v)表示这个位置是向下的指引牌。
对于每组数据，第一行是两个正整数n,m，表示迷宫有n行m列(1<=n,m<=100)。
接下来n行，每行m个字符，描述迷宫——
"."(点)表示这个位置是空白，
"<"(小于)表示这个位置是向左的指引牌，
">"(大于)表示这个位置是向右的指引牌，
"^"(异或)表示这个位置是向上的指引牌，
"v"(字母v)表示这个位置是向下的指引牌。
Output
对于每组数据，输出一行一个整数，表示至少需要修改几个指引牌，才能达到目的，如果无法实现，输出-1
Sample Input
4 2 1 ^ ^ 2 2 >v ^< 3 3 ... .^. ... 1 1 .
Sample Output
1 0 -1 0