1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| int n,m,a[MAX][MAX],x,y,c,vis[MAX][MAX],ans,_min[MAX][MAX];
int aw[4][2]={1,0,0,1,-1,0,0,-1};
bool judge(int x,int y){
if(x<1||x>n||y<1||y>n) return false;
return true;
}
void dfs(int x,int y,int d,int f){
if(x==n&&y==n){
ans = min(ans,d);
return ;
}
_min[x][y]=d;
fi(i,0,4){
int tx= x+aw[i][0],ty=y+aw[i][1];
if(judge(tx,ty) && !vis[tx][ty]){
if(a[tx][ty]==-1 && f) continue;
vis[tx][ty]=1;
if(a[tx][ty]==-1 && d+2<_min[tx][ty]){
a[tx][ty]=a[x][y];
dfs(tx,ty,d+2,1);
a[tx][ty]=-1;
}else if(a[tx][ty]==a[x][y] && d<_min[tx][ty]){
dfs(tx,ty,d,0);
}else if(d+1<_min[tx][ty]){
dfs(tx,ty,d+1,0);
}
vis[tx][ty]=0;
}
}
}
int main(){
freopen("in","r",stdin);
sf(n);sf(m);
mem(a,-1);
mem(vis,0);
mem(_min,0x3f);
fi(i,0,m){
sf(x);sf(y);sf(c);
a[x][y]=c;
}
vis[1][1]=1;ans =INF;
dfs(1,1,0,0);
if(ans==INF)pfc("-1");
else pf(ans);
return 0;
}
|