问题描述

具体描述见教材p192：Angel被人抓住关在一个迷宫了！迷宫的长、宽不超过200，迷宫中有不可以越过的墙以及监狱的看守。Angel的朋友带了一个救援队来到了迷宫中。他们的任务是：接近Angel。我们假设接近Angel就是到达Angel所有的位置。 假设移动需要1单位时间，杀死一个看守也需要1单位时间。到达一个格子以后，如果该格子有看守则一定要杀死。交给你的任务是，最少要多少单位时间，才能到达Angel所在的地方（只能向上、下、左、右4个方向移动）？

格式

输入

第1行两个整数n, m。 表示迷宫的大小为n x m。 以后n行，每行m个字符。其中“#”代表墙，“.”表示可移动， “x”表示看守，“a”表示Angel， “r”表示救援队伍。字母均为小写。

输出

1行，代表救出Angel的最短时间。如果救援小组永远不能达到Angel处，则输出“NO ANSWER”。

样例

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

13

限制

1s, 64MB.