试题历届试题剪格子（c++）

柔光的暖阳◎ 2022-12-12 04:57 211阅读 0赞

dfs（x, y, \_ans, \_sum）  
朝四个方向递归然后不行就回溯  
下面是两份代码，最下面那份带了注释，自行观看

#include <iostream>
    
    using namespace std;
    const int maxn = 1e3 + 5;
    const int INF = 1e5;
    int arr[maxn][maxn];
    int row, cal;
    int ans = INF, sum = 0; 
    bool vis[maxn][maxn];
    
    // void dfs(int x, int y, int _sum, int _ans)
    // {
        
    //     if (!arr[x][y] || vis[x][y]) return ;
    //     _sum += arr[x][y], ++_ans, vis[x][y] = true;
    //     /*
    //         若还没出现和为一半的情况，ans == INF， 不可能出现 比ans大的
    //         若出现了一种情况，那么 之后若 有 _ans > ans 无论能否组成都不考虑了
    //         _sum > sum 比较好理解 就直接不合法了
    //     */
    //     if (_ans > ans || _sum > sum) {vis[x][y] = false; return ;}
    //     /*
    //         能够到这一步的都是_ans <= ans
    //         此时_sum == sum 直接替换一下ans
    //         然后回溯就可以啦
    //     */
    //     if (_sum == sum) {ans = _ans; vis[x][y] = 0; return ;}
    //     dfs(x - 1, y, _sum, _ans), dfs(x, y - 1, _sum, _ans);
    //     dfs(x + 1, y, _sum, _ans), dfs(x, y+1, _sum, _ans);
    //     vis[x][y] = false;
    // }
    
    
    void dfs(int x, int y, int _ans, int _sum)
    {
        
        if (!arr[x][y] || vis[x][y]) return ;
        _sum += arr[x][y], ++_ans, vis[x][y] = true;
        if (_ans > ans || _sum > sum) {
        vis[x][y] = false; return ;}
        if (_sum == sum) 
        {
        
            ans = _ans;
            vis[x][y] = false;
            return ;
        }
        dfs(x - 1, y, _ans, _sum);
        dfs(x, y - 1, _ans, _sum);
        dfs(x + 1, y, _ans, _sum);
        dfs(x, y + 1, _ans, _sum);
        vis[x][y] = false;
    }
    int main()
    {
        
        ios::sync_with_stdio(false);
        //freopen("in.txt", "r", stdin);
        cin >> row >> cal;
        for (int i = 1; i <= row; i++)
        {
        
            for (int j = 1; j <= cal; j++)
            {
        
                vis[i][j] = false;
                cin >> arr[i][j];
                sum+=arr[i][j];
            }
        }
        cout << "[" << sum << "]" << endl;
        if (sum % 2 == 1)
            cout << 0 << endl;
        else 
        {
        
            sum /= 2; 
            dfs(1, 1, 0, 0);
            cout << ans << endl;
        }
        system("pause");
        return 0;
    }
    
    
    // #include <iostream>
    
    // using namespace std;
    // const int INF = 1 << 30;
    // int sum = 0;
    // int m, n, a[15][15], ans;
    // bool vis[15][15];
    
    // void dfs(int x, int y, int _sum, int _ans)
    // {
        
    //     if (!a[x][y] || vis[x][y]) return ;
    //     _sum += a[x][y], ++_ans, vis[x][y] = true;
    //     /*
    //         若还没出现和为一半的情况，ans == INF， 不可能出现 比ans大的
    //         若出现了一种情况，那么 之后若 有 _ans > ans 无论能否组成都不考虑了
    //         _sum > sum 比较好理解 就直接不合法了
    //     */
    //     if (_ans > ans || _sum > sum) {vis[x][y] = false; return ;}
    //     /*
    //         能够到这一步的都是_ans <= ans
    //         此时_sum == sum 直接替换一下ans
    //         然后回溯就可以啦
    //     */
    //     if (_sum == sum) {ans = _ans; vis[x][y] = 0; return ;}
    //     dfs(x - 1, y, _sum, _ans), dfs(x, y - 1, _sum, _ans);
    //     dfs(x + 1, y, _sum, _ans), dfs(x, y+1, _sum, _ans);
    //     vis[x][y] = false;
    // }
    // int main()
    // {
        
    //     //freopen("in.txt", "r", stdin);
    //     sum = 0;
    //     cin >> m >> n;
    //     for (int i = 0; i < m; i++)
    //         for (int j = 0; j < n; j++)
    //         {
        
    //             cin >> a[i][j];
    //             sum += a[i][j];
    //         }
    //     if (sum % 2 == 1) 
    //     {
        
    //         cout << 0 << endl;
    //         system("pause");
    //     }
    //     else 
    //     {
        
    //         sum /= 2;
    //         ans = INF;
    //         dfs(1, 1, 0, 0);
    //         cout << (ans == INF ? 0 : ans);
    //         system("pause");
    //     }
    //     return 0;
    // }