有一条蛇在它的洞里面,现在他要出来,问最少要多少步才可以移动到出口.出口的位置是(11).蛇可以弯曲的,但是它的部分必须是连接的,比如:如果它有一个部位在一个坐标,连接它那个部位的坐标一定是它的上下左右.
有多组数据.每组数据的第一行有3个数,NML(N,M)表示洞的大小N*M,L表示蛇的长度.然后下面有L行,每行两个数,表示蛇所有部位的位置.第一组是蛇的头,第L组是蛇的尾巴,也就是说是按顺序给出蛇的头至尾的位置,移动时蛇的蛇的后面一个部位要移到之前那个部位的位置.当然蛇不能走到有石头的地方且它不能走在自己身上. 然后给出一个K,表示洞里面有多少块石头.然后下面有K行,每行2个数,表示每块石头的坐标. 每个数据之间有一空行,数据以3个0表示结束.
如果蛇可以走出洞的话,那么输出最小步数,如果蛇不能走出洞,那么输出-1;