acwing::acwing2005类 参考

AcWing 2005. 马蹄铁 更多...

#include <acwing.h>

静态 Public 成员函数
static int	dfs (bool stage, char horseshoes[5][5], const bool picked[5][5], int count, int level, int x, int y, int n)
static int	main (istream &, ostream &)

详细描述

AcWing 2005. 马蹄铁

在文件 acwing.h 第 223 行定义.

成员函数说明

dfs()

int acwing::acwing2005::dfs ( bool  stage, char  horseshoes[5][5], const bool  picked[5][5], int  count, int  level, int  x, int  y, int  n  )

static

参数

stage	当前阶段 ture为寻找左括号 false为寻找右括号
horseshoes	马蹄铁方格
picked	已经走过的区域
count	当前括号字符串长度
level	括号平衡情况(当前左括号的数量-右括号的数量)
x	当前横座标
y	当前纵座标
n	座标上限

返回

当前状态下最长完全平衡括号字符串的长度

在文件 acwing.cpp 第 583 行定义.

                               {
        if(level == 0 && !stage) {
            if(count == 13) {
                printf("13");
            }
            return count;
        }
 
        pair<int, int> nexts[4] = {pair(x - 1, y), pair(x + 1, y), pair(x, y - 1),
                                   pair(x, y + 1)};
        //复制状态
        bool picked_cpy[5][5];
        memcpy(picked_cpy, picked, sizeof picked_cpy);
 
        int max          = 0;
        picked_cpy[x][y] = true;
 
        for(const auto next: nexts) {
            if(0 <= next.first && next.first < n && 0 <= next.second && next.second < n &&
               !picked_cpy[next.first][next.second]) {
                int res = 0;
                if(stage && horseshoes[next.first][next.second] == '(') {
                    res = dfs(true, horseshoes, picked_cpy, count + 1, level + 1, next.first, next.second, n);
                } else if(stage && horseshoes[next.first][next.second] == ')') {
                    res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
                } else if(!stage && horseshoes[next.first][next.second] == ')') {
                    res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
                }
                if(max < res) {
                    max = res;
                }
            }
        }
        return max;
    }

引用了 dfs().

被这些函数引用 dfs() , 以及 main().

main()

int acwing::acwing2005::main ( istream &  cin, ostream &  cout  )

static

在文件 acwing.cpp 第 564 行定义.

                                                    {
        char horseshoes[5][5];
        bool picked[5][5];
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cin >> horseshoes[i][j];
            }
        }
        memset(picked, 0, sizeof picked);
        if(horseshoes[0][0] == ')') {
            cout << 0;
            return 0;
        }
        cout << dfs(true, horseshoes, picked, 1, 1, 0, 0, n);
        return 0;
    }

引用了 dfs().

被这些函数引用 acwing::TEST().

---

该类的文档由以下文件生成:

• acwing.h
• acwing.cpp