HDU 5612 Baby Ming and Matrix games(dfs搜索) - dblank

HDU 5612 Baby Ming and Matrix games(dfs搜索)

问题描述
铭宝宝喜欢玩游戏,这两天他喜欢玩下面这个游戏了。
给出一个n*mn∗m的矩阵,矩阵的(i*2,j*2)(i∗2,j∗2) (其中i, j = 0, 1, 2...i,j=0,1,2...) 位置上为0~9的数字,矩阵中每两个数字中间有一个算术符号(+、-、*、/),其他位置用#填充。
问题是:是否能在上述矩阵中,找到一个表达式,使得表达式的计算结果为给出的sum(表达式从左到右计算)
表达式按照如下方式获取:选择一个数字作为起点,每次选择相邻的数字XX进行一次计算,把得到的结果保存在数字XX上,并选择该位置为下一个起点(同一个位置的数字不能使用22次)。
输入描述
输入T(T \leq 1,000)T(T≤1,000)表示测试组数
输入33个数,奇数n,mn,m以及整数sumsum(除0的式子是不合法的,除法规则见样例,-10^{18} < sum < 10^{18}−10
18
<sum<10
18

接下来输入nn行,每行mm个字符,表示给出的矩阵(矩阵内的数字个数\leq 15≤15)
输出描述
输出Possible,表示能够找到这样的表达式
输出Impossible,表示不能够找到这样的表达式
输入样例
3
3 3 24
1*1
+#*
2*8
1 1 1
1
3 3 3
1*0
/#*
2*6
输出样例
Possible
Possible
Possible
直接暴力dfs跑一边所有可能情况,注意在保存结果的时候直接用double会存在精度的问题,所以结果用分子和分母的形式保存,最后gcd一下和sum比较。还有就是为除法的时候除数式不可以为0的。

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
using namespace std;  
const int N = 1e2 + 10;  
const double eps = 1e-10;  
typedef long long ll;  
char s[N][N];  
int vis[N][N], run[][2] = {2, 0, -2, 0, 0, 2, 0, -2}, ok, m, n;  
ll sum;  
bool yes(int a,int b)  
{  
    if(a < 1 || a > m || b < 1 || b> n)  
        return false;  
    return true;  
}  
ll gcd(ll a, ll b)  
{  
    return b == 0 ? a : gcd(b, a%b);  
}  
void dfs(int x, int y, ll fz, ll fm)  
{  
    //cout<<fz <<" "<<fm<<endl;  
    if(fm / gcd(fz, fm) == 1 && fz/gcd(fz, fm) == sum)  
        ok = 1;  
    if(ok) return ;  
    for(int i = 0; i<4; i++)  
    {  
        int a = x + run[i][0];  
        int b = y + run[i][1];  
        if(!vis[a][b] && isdigit(s[a][b]) && yes(a, b))  
        {  
            int c = (a + x) / 2;  
            int d = (b + y) / 2;  
            int num = s[a][b] - '0';  
            if(s[c][d] == '/' && num == 0)  
                continue;  
            vis[a][b] = 1;  
  
            if(s[c][d] == '*')  
                dfs(a, b, fz*num, fm);  
            else if(s[c][d] == '+')  
                dfs(a, b, fz+fm*num, fm);  
            else if(s[c][d] == '-')  
                dfs(a, b, fz-fm*num, fm);  
            else if(s[c][d] == '/')  
                dfs(a,b, fz, fm*num);  
            vis[a][b] = 0;  
        }  
    }  
}  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        scanf("%d%d%I64d", &m, &n, &sum);  
        for(int i = 1; i<=m; i++)  
            for(int j = 1; j<=n; j++)  
                scanf(" %c", &s[i][j]);  
        ok = 0;  
        for(int i = 1; i<=m; i++)  
            for(int j = 1; j<=n; j++)  
            {  
                if(isdigit(s[i][j]))  
                {  
                    memset(vis, 0, sizeof(vis));  
                    vis[i][j] = 1;  
                    dfs(i, j, s[i][j] - '0', 1);  
                }  
            }  
        if(ok) puts("Possible");  
        else puts("Impossible");  
    }  
    return 0;  
}

 

相关文章

发表新评论