Skip to content

11339: 【原1339】general

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1339 ## 题目描述

到处memeda的儒哥整天抢高爷的零食吃。在atm队内某一场撕逼训练后,儒哥偷偷把高爷的午饭藏了起来。作为高爷尊贵的前队友,死神不忍心看高爷饿一下午肚子,于是他就打算去把可口的饭菜夺回来。

在这一个特定的空间维度里,我们生活在一个n*m的网格状的世界。为了简单起见,假设死神位于坐标点(1,1)处,并且通过某种神秘的法术,我们已经获知食物位于(n,m)的上将,想想都讨厌死了。死神可没有钱买这么多这么长的绳子,因此他希望遇上最少的分身。蠢蠢的死神只会一百以内的加减法,这种事情算也算不清了。怎么办呢?请你们帮助他呗!

输入说明

第一行唯一的整数test,表示数据组数;

接下来test块,每块第一行两个整数n,m,框定了网格图的大小;

紧接着n行,每行m个小写字母,刻画了每个格子的属性;

输出格式

输出test行,每行一个整数,即死神一路上遇上的上将分身的最少次数;

Sample input

4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd

Sample output

0
3
2
2

数据范围

对于30%的数据,n=1;

对于60%的数据,\( n、m \leq 100 \);

对于100%的数据,\( test \leq 5,n、m \leq 1000 \);

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!