Description

谢老师最近刚学完广度优先搜索bfs，知道了广搜在一个矩阵上的探索模式是像波纹一样一层层向周围扩散

 void bfs(int sx, int sy){

    queue<Node> q;

    q.push(Node{sx, sy});

    while (!q.empty()){

        Node now = q.front();

        q.pop();

        for (int i = 0; i < 4; ++i){

            int tx = now.x + dirx[i];

            int ty = now.y + diry[i];

            if (vis[tx][ty] == 0){

                q.push(Node{tx, ty});

                vis[tx][ty] = 1;

            }

        }

    }

}

但是显然谢老师的这段代码有一个致命错误——没有判断边界，也就是会无限向外拓展

比如有如下大小的矩阵，用 0 表示没走过的点(vis[x][y] == 0)，用 1 表示走过的点(vis[x][y] == 1)

 第一轮搜索以后矩阵如下

0000000

0000000

0001000

0000000

0000000

第二轮搜索以后矩阵如下

0000000

0001000

0011100

0001000

0000000

第三轮搜索以后矩阵如下

0001000

0011100

0111110

0011100

0001000

现在谢老师想知道，现在他这份没有设置范围的代码，在不考虑越界（即认为 vis 数组无穷大，代码不会因为出界报错）的情况下

第 n 轮搜索以后 vis 数组求和的结果是多少？

Input Format

输入第一行是一个整数 n，表示搜索的轮数

对于 50% 的数据，保证 1<=n<=20

对于 80% 的数据，保证 1<=n<=10000

对于 100% 的数据，保证 1<=n<=10^9

Output Format

输出一行，包含一个整数，表示答案

3

13

Source

佛山市青少年科技素养创意挑战赛 六年级模拟题