@[wangzll](/user/506524) 题目中上下左右都可以走，但你的代码在 判定是否出界 与 施展魔法 都只考虑了向右下的方向。
by xutongwei @ 2022-08-03 15:08:02
我把它当做了一个剪枝@[xutongwei](/user/223588)
by wangzll @ 2022-08-03 15:22:37
结果还是错的@[xutongwei](/user/223588)
by wangzll @ 2022-08-03 15:29:27
@[wangzll](/user/506524)
在 施展魔法 时，不能用 else，因为施展魔法后上下左右四种情况，一样要用 for 分类讨论。
把这里改了就 AC 了。（竟然没有TLE……）
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,a[1005][1005],minn = 0x3f3f3f,num[1005][1005];
int dx[] = {-1,1,0,-1,0},dy[] = {-1,0,1,0,-1};
void dfs(int x,int y,int money)
{
//<<x<<" "<<y<<" "<<money<<" "<<a[x][y]<<endl;
if(x == n&&y == n) {minn = min(minn,money);return;}
for(int i = 1;i <= 4;i++)
{
int xx = x + dx[i],yy = y + dy[i],money1 = money;
if(xx > n||yy > n || xx < 1 || yy < 1) continue;
if(a[xx][yy] != a[x][y]&&a[xx][yy] != -1) money1 ++;
else if(a[xx][yy] == -1){
if(xx == n&&yy == n) money1 += 2;
else{
for(int j = 1; j <= 4; j++){
int xxx = xx + dx[j],yyy = yy + dy[j],money2=money1;
if(xxx > n||yyy > n || xxx < 1 || yyy < 1) continue;
if(a[xxx][yyy] != -1 && !(xxx == x && yyy == y))
{
if(a[xxx][yyy] == a[x][y])money2 += 2;
else money2 += 3;
if(money2 < num[xxx][yyy]&&(a[xxx][yyy] != -1||xxx == n&&yyy == n))
{
num[xxx][yyy] = money2;
dfs(xxx,yyy,money2);
}
}
}continue;
}
}
if(money1 < num[xx][yy]&&(a[xx][yy] != -1||xx == n&&yy == n))
{
num[xx][yy] = min(num[xx][yy],money1);
dfs(xx,yy,money1);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(a,-1,sizeof a);
memset(num,0x3f3f3f,sizeof num);
for(int i = 1;i <= m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y] = z;
}
dfs(1,1,0);
if(minn == 0x3f3f3f) cout<<-1<<endl;
else cout<<minn<<endl;
return 0;
}
```
by xutongwei @ 2022-08-03 16:18:23
好耶，改了2周的题终于过了
by wangzll @ 2022-08-03 20:32:18
本来想着剪枝呢，结果把正确答案给剪掉了
by wangzll @ 2022-08-03 20:32:57