3886: 黄老师的广度优先搜索
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
黄老师最近刚学完广度优先搜索$(bfs)$，知道了广搜在一个矩阵上的探索模式是像波纹一样一层层向周围扩散
```cpp
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$ 数组求和的结果是多少？
```cpp
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$ 数组求和的结果是多少？
输入
输入第一行是一个整数 $n$，表示搜索的轮数
对于 $80\%$ 的数据，保证 $1 \leq n \leq 10000$
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^9$
输出
输出一行，包含一个整数，表示答案
样例输入 复制
3样例输出 复制
13