SCP--096

题目背景

SCP金基会的收容物逃走了，编号096的白色生物进入了试验区，特种兵九尾狐部队需要抓住096，请你帮忙算出096的逃跑路线（注：096为非智慧生物，它只会跑耗时最长的路线）

题目描述

096从左上角（1，1）出发，出口为右下角（x,y）;找出耗时最长的逃跑路线。(注：只会往下或右走)

输入格式

第一行，输入两个正整数下x和y，为试验区的大小; 第二至x+1行,每行有y个字符，“#”代表铁门，096需要2秒时间破门;“d”带表d级人员，096只需1秒杀死，“.”代表什么也没有，096从这过不需要秒数。

输出格式

第一行输出一个正整数sum，为总时长。 第二行输出路线。(如果是0秒，无需输出路线)

样例 #1

样例输入 #1

3 3
#.#
dd.
#d.

样例输出 #1

6
(1,1)->(1,2)->(1,3)->(2,3)->(3,3)

提示

0<x,y<501