2 条题解
-
0
#include<bits/stdc++.h> using namespace std; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; bool Map[110][110]; bool bk=false; int n,m; int f[110][110][4]; int stx,sty,edx,edy; void dfs(int x,int y,int t,int s) { if(s>f[x][y][t]) return; f[x][y][t]=s; if(x==edx && y==edy){bk=true;return;} else { for(int i=0;i<=3;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(Map[xx][yy]) { Map[xx][yy]=0; dfs(xx,yy,i,s+(i!=t)); Map[xx][yy]=1; } } } } int main() { scanf("%d%d",&n,&m); memset(Map,0,sizeof(Map)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x;scanf("%d",&x);Map[i][j]=(x==0); } } scanf("%d%d",&stx,&sty); scanf("%d%d",&edx,&edy); memset(f,63,sizeof(f)); Map[stx][sty]=0; bk=false;for(int i=0;i<=3;i++)dfs(stx,sty,i,0); if(bk==0) printf("-1\n"); else { int ans=999999999;for(int i=0;i<=3;i++)ans=min(ans,f[edx][edy][i]); printf("%d\n",ans); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; bool Map[110][110],bk=False; int n,m; int f[110][110][4]; int stx,sty,edx,edy; void dfs(int x,int y,int t,int s) { if(s>f[x][y][t]) return; f[x][y][t]=s; if(x==edx && y==edy){bk=True;return;} else { for(int i=0;i<=3;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(Map[xx][yy]) { Map[xx][yy]=0; dfs(xx,yy,i,s+(i!=t)) ; Map[xx][yy]=1; } } } } int main() { scanf("%d%d",&n,&m); memset(Map,0,sizeof(Map)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x;scanf("%d",&x);Map[i][j]=(x==0); } } scanf("%d%d",&stx,&sty); scanf("%d%d",&edx,&edy); memset(f,63,sizeof(f)); Map[stx][sty]=0; bk=0;for(int i=0;i<=3;i++)dfs(stx,sty,i,0); if(bk==0) printf("-1\n"); else { int ans=999999999;for(int i=0;i<=3;i++)ans=min(ans,f[edx][edy][i]); printf("%d\n",ans); } return 0; }
- 1
信息
- ID
- 778
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 90
- 已通过
- 20
- 上传者