hdu 5612 Baby Ming and Matrix games

题意: 给一个矩形，两个0~9的数字之间隔一个数学运算符(‘+’,’-‘,’*’,’/’),其中’/’表示分数除，再给一个目标的值，问是否存在从一个数字出发，以数字之间的运算符为运算，得到这个目标值；(每个数字只能用一次，其实说白了就是dfs..);可以则输出(Impossible),否则输出(Possible);

思路:坑点就是里面本来全是整数，但是一个除法运算却是分数形式，开始使用了很保险的分数保存，来避免误差的。但是无情WA了很多次。。突然发现写成了(ImPossible)…醉了，然后以为现在肯定要A了，但是还是WA了。。。(有兴趣的帮我找找bug哈！真心感谢)之后重写了一个double类型的，无奈啊(太水了)，下面是A和WA两份代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

using namespace std;

#define rep(i,n) for(int i = 1;i <= n;i++)

#define MS0(a) memset(a,0,sizeof(a))

#define esp 1e-6

int n,m,vis[][],f;

double sum;

char s[][];

int dir[][] = {{,,,-},{,,-,}};

double cal(double val,double v,char op)

{

    if(op == '+') return val + v;

    else if(op == '-') return val - v;

    else if(op == '*') return val * v;

    return val/v;

}

void dfs(int i,int j,double val)

{

    if(fabs(val - sum) < esp) f = ;

    for(int k = ;k <  && f;k++){

        int x = i + *dir[][k] , y = j + *dir[][k];

        char op = s[i + dir[][k]][j + dir[][k]];

        if(x <  || x > n || y <  || y > m || vis[x][y]) continue;

        int v = s[x][y] - '';

        if(op == '/' && v == ) continue;

        vis[x][y] = ;

        dfs(x,y,cal(val,v,op));

        vis[x][y] = ;

    }

}

int main()

{

    int T,i,j;

    cin>>T;

    while(T--){

        f= ;MS0(vis);

        scanf("%d%d%lf",&n,&m,&sum);

        rep(i,n) scanf("%s",s[i] + );

        for(i = ;i <= n && f;i += )

        for(j = ;j <= m && f;j += ){

            vis[i][j] = ;

            dfs(i,j,s[i][j] - '');

            vis[i][j] = ;

        }

        puts(f?"Impossible":"Possible");

    }

    return ;

}

Accpeted code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

using namespace std;

typedef long long ll;

#define MS0(a) memset(a,0,sizeof(a))

ll cal(ll a,ll b,char op)

{

    if(op == '+') return a + b;

    if(op =='-') return a - b;

    if(op == '*') return a * b;

}

int dir[][] = {{,,,-},{,,-,}};

char s[][];

ll sum,f;

int n,m,vis[][];

void dfs(int i,int j,ll ele,ll den)

{

    if(ele%den ==  && ele / den == sum) f = ;

    ll e = ele, d = den;

    for(int k = ;k <  && f;k++){

        //system("pause");

        int x = i + *dir[][k],y = j + *dir[][k];

        char op = s[i+dir[][k]][j+dir[][k]];

        if(x <  || x > n || y < || y > m||vis[x][y]) continue;

        ele = e,den = d;

        int val = (s[x][y]-'');

        if(op =='/'){

            if(val == ) continue;

            if(ele % val) den *= val;

            else ele /= val;

        }

        else ele = cal(ele,val,op);

        if(ele % den == ) ele /= den,den = ;

        vis[x][y] = ;

        dfs(x,y,ele,den);

        vis[x][y] = ;

    }

}

int main()

{

    int T,i,j;

    cin>>T;

    while(T--){

        MS0(vis);

        scanf("%d%d%I64d",&n,&m,&sum);

        for(i = ;i <= n;i++)

            scanf("%s",s[i] + );

        f = ;

        for(i = ;i <= n && f;i += )

            for(j = ;j <= m && f;j += ){

                vis[i][j] = ;

                dfs(i,j,(ll)(s[i][j] - ''),);

                vis[i][j] = ;

        }

        puts(f?"Impossible":"Possible");

    }

    return ;

}

WA Code

秒客网

hdu 5612 Baby Ming and Matrix games

相关文章