hdu 5612 Baby Ming and Matrix games（dfs暴力）-白红宇

hdu 5612 Baby Ming and Matrix games（dfs暴力）

阅读量：7021 次

发布时间：2019-06-28

本文共 4640 字，大约阅读时间需要 15 分钟。

Problem Description

These few days, Baby Ming is addicted to playing a matrix game.Given a n∗m matrix, the character in the matrix(i∗2,j∗2) (i,j=0,1,2...) are the numbers between 0−9. There are an arithmetic sign (‘+’, ‘-‘, ‘∗’, ‘/’) between every two adjacent numbers, other places in the matrix fill with ‘#’.The question is whether you can find an expressions from the matrix, in order to make the result of the expressions equal to the given integer sum. (Expressions are calculated according to the order from left to right)Get expressions by the following way: select a number as a starting point, and then selecting an adjacent digital X to make the expressions, and then, selecting the location of X for the next starting point. (The number in same place can’t be used twice.)

Input

In the first line contains a single positive integer T, indicating number of test case.In the second line there are two odd numbers n,m, and an integer sum(−1018
      
       <1018, divisor 0 is not legitimate, division rules see example)In the next n lines, each line input m characters, indicating the matrix. (The number of numbers in the matrix is less than 15)1≤T≤1000

Output

Print Possible if it is possible to find such an expressions.Print Impossible if it is impossible to find such an expressions.

Sample Input

33 3 241*1+#*2*81 1 113 3 31*0/#*2*6

Sample Output

Possible Possible Possible

Hint

The first sample：1+2*8=24 The third sample：1/2*6=3

Source

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

直接dfs暴力即可，注意要用double类型来计算

AC代码：

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                12 #include
                 
                  13 #include
                  
                   14 #include 
                   
                    15 using namespace std;16 #define PI acos(-1.0)17 #define max(a,b) (a) > (b) ? (a) : (b)18 #define min(a,b) (a) < (b) ? (a) : (b)19 #define ll long long20 #define eps 1e-1021 #define MOD 100000000722 #define N 2623 #define inf 1e1224 int n,m;25 double sum;26 char mp[N][N];27 int dirx[]={ 0,0,-1,1};28 int diry[]={-1,1,0,0};29 int vis[N][N],flag;30 void dfs(int x,int y,double s){31 vis[x][y]=1;32 if(fabs(s-sum)<=0.00000001){33 flag=1;34 return;35 }36 for(int i=0;i<4;i++){37 int fx = x+dirx[i],fy = y+diry[i];38 int sx = x+dirx[i]*2,sy = y + diry[i]*2;39 if(sx<0 || sx>=n || sy<0 || sy>=m || vis[sx][sy]) continue;40 if(mp[fx][fy]=='#') continue;41 double cnt = (double)(mp[sx][sy]-'0');42 if(mp[fx][fy]=='+') dfs(sx,sy,s+cnt);43 else if(mp[fx][fy]=='-') dfs(sx,sy,s-cnt);44 else if(mp[fx][fy]=='*') dfs(sx,sy,s*cnt);45 else if(mp[fx][fy]=='/') dfs(sx,sy,s/cnt);46 }47 vis[x][y]=0;48 49 }50 int main()51 {52 int t;53 scanf("%d",&t);54 while(t--){55 memset(vis,0,sizeof(vis));56 scanf("%d%d%lf",&n,&m,&sum);57 for(int i=0;i
                    
                     ='0' && mp[i][j]<='9'){64 dfs(i,j,mp[i][j]-'0');65 if(flag) break;66 }67 }68 if(flag) break;69 }70 if(flag) printf("Possible\n");71 else printf("Impossible\n");72 }73 return 0;74 }

View Code

别人的AC代码：

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
             7 #include
             
               8 #include
              
                9 #include
               
                10 #include
                
                 11 #include
                 
                  12 using namespace std;13 #define rep(i,n) for(int i = 1;i <= n;i++)14 #define MS0(a) memset(a,0,sizeof(a))15 #define esp 1e-616 int n,m,vis[35][35],f;17 double sum;18 char s[35][35];19 int dir[2][4] = { { 0,1,0,-1},{ 1,0,-1,0}};20 double cal(double val,double v,char op)21 {22 if(op == '+') return val + v;23 else if(op == '-') return val - v;24 else if(op == '*') return val * v;25 return val/v;26 }27 void dfs(int i,int j,double val)28 {29 if(fabs(val - sum) < esp) f = 0;30 for(int k = 0;k < 4 && f;k++){31 int x = i + 2*dir[0][k] , y = j + 2*dir[1][k];32 char op = s[i + dir[0][k]][j + dir[1][k]];33 if(x < 1 || x > n || y < 1 || y > m || vis[x][y]) continue;34 int v = s[x][y] - '0';35 if(op == '/' && v == 0) continue;36 vis[x][y] = 1;37 dfs(x,y,cal(val,v,op));38 vis[x][y] = 0;39 }40 }41 int main()42 {43 int T,i,j;44 cin>>T;45 while(T--){46 f= 1;MS0(vis);47 scanf("%d%d%lf",&n,&m,&sum);48 rep(i,n) scanf("%s",s[i] + 1);49 for(i = 1;i <= n && f;i += 2)50 for(j = 1;j <= m && f;j += 2){51 vis[i][j] = 1;52 dfs(i,j,s[i][j] - '0');53 vis[i][j] = 0;54 }55 puts(f?"Impossible":"Possible");56 }57 return 0;58 }