题意：给一个n*m的矩形，每个方格要不为空，要不有金币，每次你可以将矩形所有金币选择一个方向（上下左右）移动一格，如果移动后有金币出矩形了，则该金币消失。问最少步骤使得方格金币恰好为K
( 1≤n,m≤30 )

解法：枚举每个子矩形，如果该子矩形含有金币数量恰好为K，则贪心算出得到该子矩形的代价，即上下移动算一次代价，左右移动算一次代价，两次代价都分别等于 移动次数最小值*2＋移动次数最大值

Code

#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           using namespace std; typedef long long ll; class DropCoins{ public: int a[50][50]; int getMinimum(vector
          
            b, int k){ memset(a,0,sizeof(a)); for(int i = 0; i < b.size(); i++){ int t = 0; for(int j = 0; j < b[0].length(); j++){ if(b[i][j] == 'o') ++t; a[i][j] = t; if(i > 0) a[i][j] += a[i-1][j]; } } int ans = 1e9; for(int i1 = 0; i1 < b.size(); i1++){ for(int j1 = 0; j1 < b[0].length(); j1++){ for(int i2 = i1; i2 < b.size(); i2++){ for(int j2 = j1; j2 < b[0].length(); j2++){ int a1 = a[i2][j2]; if(i1 > 0) a1 -= a[i1-1][j2]; if(j1 > 0) a1 -= a[i2][j1-1]; if(i1 > 0 && j1 > 0) a1 += a[i1-1][j1-1]; if(a1 == k) { int t1, t2, anst = 0; t1 = i1, t2 = (int)b.size() - i2 - 1; anst += 2 * min(t1, t2) + max(t1, t2); t1 = j1, t2 = (int)b[0].length() - j2 - 1; anst += 2 * min(t1, t2) + max(t1, t2); ans = min(ans, anst); } } } } } if(ans == 1e9) ans = -1; return ans; } };
          
         
        
       
      
     
    
   

?