HDU2187(贪心)

题目链接

传送门

解题思路

为了求得最多的重量,所以我们一定是单价便宜的优先考虑,于是按单价从小到大排个序。如果当前经费n大于0,那么分两种情况:(1)这种大米的单价 * 重量 <= n ,也就是说我即便把这种大米买光,经费还会有剩余,那么此时直接更新 n -= q[i].mon * q[i].wei,
ans += q[i].wei 。 (2)若这种大米的单价 * 重量 > n ,也就是说我现有的经费无法买光所有大米,那么我就要按比例来买了,算出当前剩余经费能够买多少斤的大米,然后ans += k , n -= k * q[i].mon就可以了。
最后注意把n在一开始就按double类型输入,方便后边的减法运算。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  

struct node  
{  
    int mon;  
    int wei;  
}q[10001];  

bool cmp(node a , node b)  
{  
    return a.mon < b.mon;  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        double n;  
        int m;  
        scanf("%lf%d",&n,&m);  
        for(int i = 0 ; i < m ; i++)  
        {  
            scanf("%d%d",&q[i].mon , &q[i].wei);  
        }  
        sort(q , q + m , cmp);  
        double ans = 0.0;  
        int i = 0;  
        while(n - EPS > 0)  
        {  
            if(n < q[i].mon * q[i].wei)  
            {  
                double k = n / (q[i].mon * q[i].wei) * q[i].wei;  
                ans += k;  
                n -= k * q[i].mon;  
            }  
            else  
            {  
                ans += q[i].wei;  
                n -= q[i].wei * q[i].mon;  
            }  
            i++;  
        }  
        printf("%.2lf\n",ans);  
    }  
}

HDU2391(简单dp)

题目链接

传送门

题目大意

题目大意就是给你一个n * m的矩阵,问你每次只能走右、下、右下这三个方向,从坐上出发到达右下,每个格子有相应的金币数,问最多能得到多少金币。

解题思路

根据dp的思想,对任意一个状态,我可以推导它的前一个状态。对于本题来说,我们还可以进一步优化,因为规定每个格子的金币数为正数,所以当你选择直接走右下这个策略并不是最优的,我们不妨走两个格子到达右下,总比一个格子要好得多(没准多走的那个格子有金币呢)。
状态转移方程dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
最后注意每组样例结束后都要有一个空行,不然报PE。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
int maps[1111][1111];  
int dp[1111][1111];  

int n , m;  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    int cas = 1;  
    while(T--)  
    {  
        scanf("%d%d",&n,&m);  
        for(int i = 0 ; i < n ; i ++)  
        {  
            for(int j = 0 ; j < m ; j ++)  
                scanf("%d",&maps[i][j]);  
        }  
        int ans = 0;  
        for(int i = 0 ; i < n ; i ++)  
        {  
            for(int j = 0 ; j < m ; j ++)  
            {  
                maps[i][j] += max(maps[i-1][j],maps[i][j-1]);  
            }  
        }  
        printf("Scenario #%d:\n%d\n\n",cas++ , maps[n-1][m-1]);  
    }  
}  

HDU2570(贪心)

题目链接

传送门

解题思路

以第三个样例为例,浓度分别为20 20 30,那么混合后的浓度应该为20 20 23 。先对原有浓度从小到大排序,求混合浓度时要先换算出百分比,然后乘以体积,即b[i] = a[i] / 100.0 * v 。最后循环遍历比较下就可以了。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
int a[101];  
double b[101];  
int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n , v , w;  
        scanf("%d%d%d",&n,&v,&w);  
        double sumt = 0;  
        double sumv =0;  
        for(int i = 0 ; i < n  ; i ++)  
        {  
            scanf("%d",&a[i]);  
        }  
        sort(a , a + n);  
        for(int i = 0  ; i < n ; i ++)  
        {  
            sumt += a[i] / 100.0 * v;  
            sumv += v;  
            b[i] = sumt / (double)sumv;  
        }  
        int cntv = 0;  
        double concer = 0.00;  
        for(int i = 0 ; i < n ; i ++)  
        {  
            if(b[i] * 100 < w)  
            {  
                cntv += v;  
                concer = b[i];  
            }  
        }  
        printf("%d %.2lf\n", cntv , concer);  
    }  
}  

HDU2600(贪心)

题目链接

传送门

题目大意

给你一个p到q的区间,然后给出n次战役的起始时间,问在区间p~q中没有战争的最大年份是多少年,如果群都有
战争,输出Badly!

解题思路

这道题很有可能被卡超时或者运行错误。抽象为一个线段上的区间覆盖问题。我们对时间的结束时间按从小到大排序。分四种情况考虑:
(1)如果最大的结束时间 < 给定的 q ,那么最大年份就是 q 。
(2)如果最大的结束时间 == q , 最小的开始时间 == q ,那说明整个线段f覆盖满了,输出Badly!
(3)如果覆盖的线段之间出现间隙,即q[i].start > q[i-1].end,那么输出q[i].start – 1。
(4)如果最后最小的开始时间 > p,那么输出q[0] .start – 1。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  

struct node  
{  
    int a;  
    int b;  
    char str[100];  
}q[10001];  

bool cmp(node x , node y)  
{  
    return x.b < y.b;  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int n , start , ends;  
    while(~scanf("%d%d%d",&n,&start,&ends))  
    {  
        for(int i = 0 ; i < n ; i ++)  
        {  
            scanf("%d%d",&q[i].a , &q[i].b);  
            cin.getline(q[i].str , 100);  
        }  
        sort(q , q + n , cmp);  
        if(q[n-1].b < ends)  
        {  
            printf("%d\n",ends);  
            continue;  
        }  
        if(q[n-1].b == ends && q[0].a == start)  
        {  
            printf("Badly!\n");  
            continue;  
        }  
        int flag = 0;  
        for(int i = n - 1 ; i >= 1 ; i --)  
        {  
            if(q[i].a > q[i-1].b)  
            {  
                printf("%d\n",q[i].a - 1);  
                flag = 1;  
                break;  
            }  
        }  
        if(flag)  
            continue;  
        else  
        {  
            if(q[0].a > start)  
                printf("%d\n",q[0].a - 1);  
        }  
    }  
}  

HDU2522(hash)

题目链接

传送门

解题思路

题目求循环节,用hash求解。首先把hash[0]和hash[1]置为1,每步先对k乘10对n取商输出,再k对n取余,模拟除法的运算过程。
并把相应的hash[k]置为1,如果出现已经访问过的hash[k]为1,说明出现循环节,跳出。
注意n可能为负。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
const int maxn = 100001;  
int hash[maxn];  

void solve(int n)  
{  
    if(n < 0)  
    {  
        printf("-");  
        n *= -1;  
    }  
    if(n == 1)  
    {  
        printf("1\n");  
        return;  
    }  
    memset(hash , 0 , sizeof(hash));  
    int k = 1;  
    hash[1] = 1;  
    hash[0] = 1;  
    printf("0.");  
    while(1)  
    {  
        k *= 10;  
        printf("%d",k / n);  
        k %= n;  
        if(hash[k])  
            break;  
        hash[k] = 1;  
    }  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        solve(n);  
        printf("\n");  
    }  
}  

HDU1800(hash)

题目链接

传送门

题目大意

题意是说有n个士兵要飞去火星,每个士兵对应一个等级,抽象为小于关系的集合,也就是具有小于关系的元素在同一个集合里,问最少需要多少个集合。

解题思路

可以用hash算法,但是在这里我们也可以发现,求最小的集合数,也就是求重复数字最大的长度,比如1 4 4 6 6 6,这里6重复了3次,重复次数最多, 所以我们最少要用到3个小于关系的集合。 对数组从小到大排序,求出数字最多的重复次数。因为比较时从下标为1开始比较,所以在循环一遍后,还要做maxx和cnt的比较,为了防止1 1 1 1这种 情况出现。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
int a[30001];  
int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int n;  
    while(~scanf("%d",&n))  
    {  
        for(int i = 0 ; i < n ; i ++)  
            scanf("%d",&a[i]);  
        sort(a , a + n);  
        int cnt = 1;  
        int maxx = -INF;  
        for(int i = 1 ; i < n ; i ++)  
        {  
            if(a[i] == a[i-1])  
                cnt ++;  
            if(a[i] != a[i-1] )  
            {  
                if(cnt > maxx)  
                    maxx = cnt;  
                cnt = 1;  
            }  
        }  
        if(cnt > maxx)  
            maxx = cnt;  
        printf("%d\n",maxx);  
    }  
}  

HDU1496(hash)

题目链接

传送门

题目大意

题意就是满足公式的x1,x2,x3,x4有多少种。

解题思路

暴力O(n^4)超时·····hash优化···直接降到了O(n^2)····· 可以建立两个数组,首先计算a * x1 ^ 2 + b * x2 ^ 2,正数存入hash1,负数存入hash2。然后计算c * x3 ^ 2 + d * x4 ^ 2,如果是正数则在hash2查找, 负数在hash1查找。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
const int maxn = 1000001;  
int hash1[maxn];  
int hash2[maxn];  
int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int a , b , c , d;  
    while(~scanf("%d%d%d%d" , &a , &b , &c , &d))  
    {  
        int cnt = 0;  
        if( (a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0) )  
        {  
            printf("0\n");  
            continue;  
        }  
        memset(hash1 , 0 , sizeof(hash1));  
        memset(hash2 , 0 , sizeof(hash2));  
        for(int i = 1 ; i <= 100 ; i ++)  
        {  
            for(int j = 1 ; j <= 100 ; j ++)  
            {  
                int k = a * i * i + b * j * j;  
                if(k >= 0)  
                    hash1[k] ++;  
                else  
                    hash2[-k] ++;  
            }  
        }  
        for(int i = 1 ; i <= 100 ; i ++)  
        {  
            for(int j = 1 ; j <= 100 ; j ++)  
            {  
                int k = c * i * i + d * j * j;  
                if(k > 0)  
                    cnt += hash2[k];  
                else  
                    cnt += hash1[-k];  
            }  
        }  
        printf("%d\n",cnt * 16);  
    }  
}  

HDU1264(hash)

题目链接

传送门

题目大意

题意是说给你矩形互为对顶角的两个点坐标,每次(-1,-1,-1,-1)则输出这个图形覆盖了多少1*1的正方形,重复覆盖只记一次。 以(-2,-2,-2,-2)结束输入。

解题思路

用hash把每个11的正方形映射到该正方形四个顶角的其中一个,也就意味着用一个点是否被标记来判断这个11的区域是否被覆盖, 这样就可以开一个二维数组来模拟平面。 另外再补充一点,按输入坐标的顺序来说的话,你要求x1 < x2 && y1 < y2其实还是同一个矩形·····比如7 5 8 10这个输入。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
int hash[1111][1111];  
int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int x1 , x2 , y1 , y2 , flag;  
    while(~scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2))  
    {  
        memset(hash , 0 , sizeof(hash));  
        flag = 0;  
        int cnt = 0;  
        while(x1 != -1 && y1 != -1 && x2 != -1 && y2 != -1)  
        {  
            if(x1 == -2 && y1 == -2 && x2 == -2 && y2 == -2)  
            {  
                flag = 1;  
                break;  
            }  
            if(x1 > x2)  
            {  
                int t = x1;  
                x1 = x2;  
                x2 = t;  
            }  
            if(y1 > y2)  
            {  
                int t = y1;  
                y1 = y2;  
                y2 = t;  
            }  
            for(int i = x1 ; i < x2 ; i ++)  
            {  
                for(int j = y1 ; j < y2 ; j ++)  
                {  
                    hash[i][j] = 1;  
                }  
            }  
            scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2);  
        }  
        for(int i = 0 ; i < 1110 ; i ++)  
        {  
            for(int j = 0 ; j < 1110 ; j ++)  
            {  
                if(hash[i][j])  
                    cnt ++;  
            }  
        }  
        printf("%d\n",cnt);  
        if(flag)  
            break;  
    }  
}  

HDU1075(map映射)

题目链接

传送门

题目大意

给你一个字典部分,再给你一个文本部分,要求按照字典把火星文转换为英文,如果不在字典里那直接输出原文, 标点符号原样输出。

解题思路

这里用isalpha函数判断当前字符是否为字母,如果是字母的话,该函数会返回一个非0的值。如果当前是字母,下一个是标点符号,那么用map判 断是否在字典里有对应的英文字符串,有的话输出英文字符串,否则原样输出。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
map<string , string> m;  
int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    string start;  
    cin >> start;  
    string eng , mar;  
    while(cin >> eng)  
    {  
        if(eng == "END")  
            break;  
        cin >> mar;  
        m[mar] = eng;  
    }  
    string s;  
    cin >> s;  
    getchar();  
    string txt , trans;  
    while(getline(cin , txt))  
    {  
        if(txt == "END")  
            break;  
        for(int i = 0 ; i < txt.size() ; i ++)  
        {  
            if(isalpha(txt[i]))  
            {  
                trans += txt[i];  
                if(!isalpha(txt[i+1]))  
                {  
                    if(m[trans] != "")  
                        cout << m[trans];  
                    else  
                        cout << trans;  
                    trans.clear();  
                }  
            }  
            else  
                cout << txt[i] ;  
        }  
        cout << endl;  
    }  
}  

HDU1026(bfs+优先级队列)

题目链接

传送门

题目大意

题意可以抽象为一个n * m矩阵,左上角(0 , 0)为入口,右下角(n-1 , m-1)为出口,’.’代表格子能走,’X’代表格子不能走, ‘n’代表走过当前格子需要消耗n秒时间,问是否能通过迷宫。如果能,那么请输出总共时间,并把路径输出。

解题思路

首先开一个结构体pre来保存走过的路径,vis标记是否走过。每次向四个方向广搜,如果下标不越界+没被标记+不是’X’,那 么就可以走。如果是’.’的话,记录下它的前驱,时间+1;如果是’n’,那么记录前驱时时间依据n值而定。最后如果搜到右下角(n-1,m-1)时,返回输出。注:bfs刚开 始时要清空队列。 输出时递归输出。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  

struct node  
{  
    int x;  
    int y;  
    int time;  
    friend bool operator < (node a , node b)  
    {  
        return a.time > b.time;  
    }  
}pre[1111][1111];  

char maps[1111][1111];  
int vis[1111][1111];  
int d[4][2] = {-1 , 0 , 0 , 1 , 1 , 0 , 0 , -1};  
int step;  
int n , m;  
priority_queue<node> q;  

void bfs()  
{  
    while(!q.empty())  
        q.pop();  
    node t1 , t2;  
    t1.x = 0;  
    t1.y = 0;  
    t1.time = 0;  
    pre[0][0].x = -1;  
    pre[0][0].y = -1;  
    pre[0][0].time = 0;  
    q.push(t1);  
    while(!q.empty())  
    {  
        t1 = q.top();  
        q.pop();  
        for(int i = 0 ; i < 4 ; i ++)  
        {  
            t2.x = d[i][0] + t1.x;  
            t2.y = d[i][1] + t1.y;  
            if(t2.x >= 0 && t2.x < n && t2.y >= 0 && t2.y < m && !vis[t2.x][t2.y] && maps[t2.x][t2.y] != 'X')  
            {  
                if(maps[t2.x][t2.y] == '.')  
                {  
                    t2.time = t1.time + 1;  
                    pre[t2.x][t2.y].x = t1.x;  
                    pre[t2.x][t2.y].y = t1.y;  
                    pre[t2.x][t2.y].time = 0;  
                    vis[t2.x][t2.y] = 1;  
                    q.push(t2);  
                }  
                else if(maps[t2.x][t2.y] >= '1' && maps[t2.x][t2.y] <= '9')  
                {  
                    t2.time = t1.time + (maps[t2.x][t2.y] - '0') + 1;  
                    pre[t2.x][t2.y].x = t1.x;  
                    pre[t2.x][t2.y].y = t1.y;  
                    pre[t2.x][t2.y].time = maps[t2.x][t2.y] - '0';  
                    vis[t2.x][t2.y] = 1;  
                    q.push(t2);  
                }  
                if(t2.x == n - 1 && t2.y == m - 1)  
                {  
                    step = t2.time;  
                    printf("It takes %d seconds to reach the target position, let me show you the way.\n" , step);  
                    return;  
                }  
            }  
        }  
    }  
}  

void path(int x , int y , int len)  
{  
    if(len > 0)  
    {  
        if(pre[x][y].time -- != 0 )  
        {  
            path(x , y , len -  1);  
            printf("%ds:FIGHT AT (%d,%d)\n", len , x , y);  
        }  
        else  
        {  
            path(pre[x][y].x , pre[x][y].y , len - 1);  
            printf("%ds:(%d,%d)->(%d,%d)\n" , len , pre[x][y].x , pre[x][y].y , x , y);  
        }  
    }  
}  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  

    while(~scanf("%d%d",&n,&m))  
    {  
        for(int i = 0 ; i < n ; i ++)  
            scanf("%s",maps[i]);  
        step = -1;  
        memset(vis , 0 , sizeof(vis));  
        vis[0][0] = 1;  
        bfs();  
        if(step == -1)  
        {  
            printf("God please help our poor hero.\nFINISH\n");  
            continue;  
        }  
        path(n - 1 , m - 1 , step);  
        printf("FINISH\n");  
    }  
}