1 条题解
-
0
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; int m,n; int chess[105][105]; bool vis[105][105]; int ans[105][105]; void dfs(int x,int y,int col,int mag,int sum){ if(sum>=ans[x][y]) return ; ans[x][y]=sum; if(x==m&&y==m){ return ; } for(int i=0;i<4;i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx<1||nx>m||ny<1||ny>m||vis[nx][ny]==1) continue; if(chess[nx][ny]==col){ vis[nx][ny]=1; dfs(nx,ny,col,0,sum); vis[nx][ny]=0; }else if(chess[nx][ny]==-1){ if(mag==0){ vis[nx][ny]=1; dfs(nx,ny,col,1,sum+2); vis[nx][ny]=0; } }else{ vis[nx][ny]=1; dfs(nx,ny,chess[nx][ny],0,sum+1); vis[nx][ny]=0; } } } int main(){ memset(chess,-1,sizeof(chess)); memset(ans,0x3f,sizeof(ans)); int x,y,c; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>x>>y>>c; chess[x][y]=c; } vis[1][1]=1; dfs(1,1,chess[1][1],0,0); if(ans[m][m]==0x3f3f3f3f){ cout<<-1; }else{ cout<<ans[m][m]; } return 0; }
信息
- ID
- 706
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 81
- 已通过
- 25
- 上传者