a了3个点
其他全wa
by HUANG_si @ 2019-09-22 16:15:20
这题当年我也是15分。。别用这题学dfs,这题应该用来学bfs呀。。
by linlin @ 2019-10-03 19:17:03
//DFS 代码,要注意不要在里面转圈
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define maxn 100+10
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int f[maxn][maxn];
int a[maxn][maxn];
int m,n;
int ans=inf;
void dfs(int x,int y,int sum,bool flag){
if(x<1||y<1||x>m||y>m)return;
if(sum>=f[x][y])return;
f[x][y]=sum;
if(x==m&&y==m)ans=min(ans,sum);
for(int i=0;i<=3;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(a[nx][ny]){
if(a[nx][ny]==a[x][y])
dfs(nx,ny,sum,false);
else dfs(nx,ny,sum+1,false);
}
else{
if(flag==false){
a[nx][ny]=a[x][y];
dfs(nx,ny,sum+2,true);
a[nx][ny]=0;
}
}
}
}
int main(){
memset(f,0x7f,sizeof(f));
cin>>m>>n;
for(int i=1;i<=n;i++){
int x,y,c;
cin>>x>>y>>c;
a[x][y]=c+1;
}
dfs(1,1,0,false);
if(ans==inf)cout<<"-1"<<endl;
else cout<<ans<<endl;
return 0;
}
by chenxing666 @ 2019-10-27 09:31:10
此代码要记忆化
by chenxing666 @ 2019-10-27 09:31:59
@[chenxing666](/user/161901) 希丰展?使MD
by GoldenFishX @ 2019-11-13 20:56:38