惊现小糯米
by lu_run_ting @ 2020-04-16 08:52:40
bfs?这题不是DP吗
by lu_run_ting @ 2020-04-16 08:53:15
MLE是爆内存吧？
by Andysun06 @ 2020-04-16 08:54:26
莫非是无限搜索导致内存耗尽？
by Andysun06 @ 2020-04-16 08:56:21
@[lu_run_ting](/user/54770) 我dfs直接RE
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int dir[2][2] = {{0, 1}, {1, 0}};
int N, map[10][10] = {};
bool book[10][10] = {};
long long dfs(int x, int y, long long num, int amap[10][10], bool first)
{
num += amap[x][y];
amap[x][y] = 0;
long long maxn = 0;
if (x == N && y == N)
{
switch (first)
{
case true:
return num + dfs(1, 1, 0, amap, false);
break;
default:
return num;
break;
}
}
for (int i = 0; i < 2; i++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx > 0 && yy > 0 && !book[xx][yy])
{
book[xx][yy] = true;
maxn = max(dfs(xx, yy, num, amap, first), maxn);
book[xx][yy] = false;
}
}
return maxn;
}
int main()
{
cin >> N;
int a, b, c;
do
{
cin >> a >> b >> c;
map[a][b] = c;
} while (a != 0 || b != 0 || c != 0);
cout << dfs(1, 1, 0, map, true);
return 0;
}
```
by 01bit @ 2020-04-16 09:42:48
@[lu_run_ting](/user/54770) ???我咋了
by 小糯米 @ 2020-04-16 10:33:12
@[bit01](/user/338147)
RE就是炸栈了，你每层dfs都自带数组（加起来一共一百多个变量），dfs叠加次数过多，可以试试inline内联
但是还是建议DP或者记忆化搜索，纯dfs过不了的
by zjjws @ 2020-04-16 16:25:28
@[zjjws](/user/73551) dp不会啊
by 01bit @ 2020-04-17 11:37:48
@[bit01](/user/338147)
题解里讲的都很清楚的吧，去学就是了，之后做多了就有感觉了
by zjjws @ 2020-04-17 13:22:14
@[bit01](/user/338147)
搜索大多数情况是用来骗分的（至少我是）
by zjjws @ 2020-04-17 13:23:25