#PQJ161x4146. QOJ 161_4146

    ID: 2668 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2012广搜最短路

QOJ 161_4146

象棋(chess) 题目描述 小云和小南两姐妹从小喜欢下象棋,现在作为象棋高手的她们,已经不屑于玩平常的象棋了,于是 她们便开始用棋盘和棋子玩各种各样的新游戏。 今天天气晴朗,阳光明媚,她们将在n * m 的棋盘上进行游戏。 棋盘上有k 颗棋子和若干有障碍格子,令棋盘左上角格子坐标为(1, 1),右下角格子坐标为(n, m), 参数a、b 规定了所有棋子的走法:在(x, y)的棋子下一步能走到(x + a, y + b), (x + a, y - b), (x – a, y + b), (x – a, y – b), (x + b, y + a), (x + b, y - a), (x – b, y + a), (x – b, y – a)这八个格子中的一个,棋子任何时候不 能跃出棋盘或走到有障碍的格子上。 这k 颗棋子是相同的,小云和小南的目标是用最少步数把所有棋子移动到特定格子,要求移动过 程中不能出现多颗棋子同时在某一格的情况。 她们已经想出步数较少方案,但无法确定这是否为最少步数,所以向作为程序员的你求助。 输入格式 第一行五个空格隔开的整数n、m、k、a 以及b; 接下来n 行,每行为长度m 的字符串,描述棋盘,‘.’表示没有障碍的格子,‘’表示有障碍的 格子; 接下来k 行,每行两个整数x 和y,分别表示k 颗棋子的初始位置; 接下来k 行,每行两个整数x 和y,分别表示k 颗棋子的目标位置。 输出格式 一个整数,为把所有棋子移动到’t’位置的最少步数,数据保证有解。 输入样例 1 8 2 2 0 ....... 1 1 1 3 1 5 1 7

输出样例 4

样例说明 一可行方案如下:第二颗棋子向右跳两步,随后第一颗棋子向右跳两步,共4 步。值得注意的是, 第一颗棋子向右跳三步,随后第二颗棋子向右跳一步的方案尽管能把棋子都移动到目标位置,但途中 两颗棋子曾经同时在(1, 3),违反了规则,所以不能选用此方案。

数据范围 其中20%的数据,n * m ≤ 20; 另外10%的数据,n = 1; 对于100%的数据,n、m ≤ 100,k ≤ 500。