6476：自动驾驶系统

题目描述

一家科技公司有一块试验地用于测试自动驾驶系统。试验地由$n\times m$个格子组成，从上到下依次编号为第$1$到$n$行，从左到右依次编号为第$1$到$m$列。试验车位于其中的某个格子上，每次自动驾驶系统可以控制汽车往上下左右移动一格。汽车不能走出边界，也不能碰到障碍格。

你需要编写自动驾驶系统中的导航部分。在测试的一开始，试验地里没有任何障碍。你的程序会依次收到$q$条信息，它们的格式是以下两种之一：

? x y，表示询问从第$1$行第$1$列的格子出发，到达第$x$行第$y$列的格子最少需要移动多少次。
* x y，表示第$x$行第$y$列的格子变成了障碍格。

输入解释

第一行包含一个正整数$T(1\leq T\leq 5)$，表示测试数据的组数。

每组数据第一行包含三个正整数$n,m,q(1\leq n,m\leq 50,1\leq q\leq 100000)$，表示试验地的尺寸以及信息的数量。

接下来$m$行，每行描述一条信息。其中$1\leq x,y\leq n$，保证每个格子不会被重复变成障碍格多次，且$(1,1)$不会变成障碍格。

输出解释

对于每个询问输出一行一个整数，即最少移动次数，若无法到达请输出$-1$。

输入样例

输出样例

2
2
-1

来自杭电HDUOJ的附加信息

Author	Claris
Recommend	liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 Championship

源链接： HDU-6476

最后修改于 2020-10-25T23:31:41+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
4000/2000MS(Java/Others)	65535/102400K(Java/Others)