是TLE还是WA?
by Eliboy @ 2023-05-18 18:27:34
@[Eliboy](/user/671846) TLE 现在70分了,代码帮忙再看看:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define f(a,c,b) for(int a = c;a<=b;a++)
int mp[1010][1010];
int vis[1010][1010];
int jiyi[1010][1010];
int tx[4] = {0,1,0,-1};
int ty[4] = {1,0,-1,0};
int m,n;
int ans = INT_MAX;
int dfs(int x,int y,int coin,bool magic)
{
if(jiyi[x][y] != -1 && jiyi[x][y] < coin)
{
return 0;
}
if(jiyi[x][y] == -1)
{
jiyi[x][y] = coin;
}
else
{
jiyi[x][y] = min(jiyi[x][y],coin);
}
for(int i = 0;i<4;i++)
{
int nx = x+tx[i]; int ny = y+ty[i];
if(nx >= 1 && ny >= 1 && nx <= m && ny <= m && vis[nx][ny] != 1 && mp[nx][ny] != 0)
{
vis[nx][ny] = 1;
dfs(nx,ny,coin + abs(mp[x][y] - mp[nx][ny]),0);
vis[nx][ny] = 0;
}
else if(mp[nx][ny] == 0 and magic == 0)
{
if(nx >= 1 && ny >= 1 && nx <= m && ny <= m && vis[nx][ny] != 1)
{
vis[nx][ny] = 1;
mp[nx][ny] = mp[x][y];
dfs(nx,ny,coin+2,1);
mp[nx][ny] = 0;
vis[nx][ny] = 0;
}
}
}
return 0;
}
int main()
{
cin >> m >> n;
int x,y,z;
memset(jiyi,-1,sizeof jiyi);
f(i,1,n)
{
cin >> x >> y >> z;
mp[x][y] = z+1;
}
dfs(1,1,0,0);
cout << jiyi[m][m] << '\n';
}
```
by I_AM_Nigger @ 2023-05-19 12:37:16
@[I_AM_Nigger](/user/932569) 不用了,我 if(jiyi[x][y] != -1 && jiyi[x][y] < coin) 写错了应该写成 if(jiyi[x][y] != -1 && jiyi[x][y] <= coin)
by I_AM_Nigger @ 2023-05-19 12:58:00
我用的是记忆化搜索
by Eliboy @ 2023-05-19 22:27:37