SP14833 FOXWOLF - The Fox and the Wolf

在一片宁静的森林里，住着一只狐狸和一只狼。人们往往以为狼会猎杀狐狸——但实际上，它们都是性情温和的动物，相处得非常融洽。事实上，它们的礼貌好到如果不凑巧相遇，它们会停下来进行长达 $C$ 分钟（$1 \leq C \leq 9$）的愉快交谈。 狐狸和狼的森林是一个矩形区域，东边长 $N$ 公里，北边宽 $M$ 公里（$1 \leq N, M \leq 20$）。这个区域被划分为一个网格，每个格子边长为 1 公里。每个格子可能是草地（用‘.’表示），布满刺（‘B’），被树木阻挡（‘T’），是狐狸的家（‘F’），是狼的家（‘W’），目前有狐狸（‘f’），或目前有狼（‘w’）。 一天繁忙"工作"（即在脑海中解决复杂的计算机科学问题）结束后，两只动物都希望尽快回到自己的住处。每分钟，它们可以向北、东、南、西行走 1 公里，或者选择待在原地——但它们无法进入被树林阻挡的格子，也不能光顾对方的家（以免显得无礼）。它们也不愿走出森林之外，因为外面有些嫉妒它们智慧的人类在徘徊。 每当狐狸或狼从一个被刺的格子走到草地时，它需要停下来快速清理身上的刺花费 $B$ 分钟（$1 \leq B \leq 9$）。如果它们在路上遇见，也要停下来聊会天。虽然格子很大，但动物总会走到其中心才继续前进。这意味着，如果它们在同一时间到达同一格子，或者在移动过程中互换位置，就会相遇并开启一场谈话。只要它们聊天过一次，就无需再聊，这样礼节就能得到满足。两只动物都非常擅长同时处理多种任务，能一边聊天一边清理身上刺。 每只动物都想尽快到家，但与此同时也会考虑对方的时间。因此，它们会合作以尽量减少到家的整体时间。作为天才动物，它们会立刻在脑中算出这个最短时间。然而，对于你这个旁观者来说，可能要编写程序来找到这个答案。

第一行：4 个整数，分别是 $N$、$M$、$C$ 和 $B$。 接下来有 $N$ 行，每行 $M$ 个字符，代表森林的一行状态。

输出一个整数，代表狐狸和狼同时到家所需的最短时间（以分钟计）。如果根本无法同时回家，则输出 -1。 **本翻译由 AI 自动生成**