1 条题解
-
0
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 35 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int n,m; int map[N][N]; ll num[N][N]; int f[N][N]; int v[N][N]; struct point { int x,y; }st,ed; bool canarrive[N][N][N][N]; int xx[9]={0,-1,-2,-2,-1,1,2,2,1}; int yy[9]={0,-2,-1,1,2,2,1,-1,-2}; void floodfill(int x,int y) { memset(v,0,sizeof(v)); queue<point>q; point tmp; tmp.x=x,tmp.y=y; q.push(tmp); while(!q.empty()) { point u=q.front(); q.pop(); for(int i=1;i<=8;i++) { tmp.x=u.x+xx[i],tmp.y=u.y+yy[i]; if(tmp.x<=0||tmp.y<=0||tmp.x>n||tmp.y>m||v[tmp.x][tmp.y])continue; if(!map[tmp.x][tmp.y]||(tmp.x==ed.x&&tmp.y==ed.y)) { canarrive[x][y][tmp.x][tmp.y]=1; }else if(map[tmp.x][tmp.y]==1) { q.push(tmp); v[tmp.x][tmp.y]=1; } } } } void bfs() { memset(v,0,sizeof(v)); queue<point>q; q.push(st); v[st.x][st.y]=1; f[st.x][st.y]=0; num[st.x][st.y]=1; while(!q.empty()) { point u=q.front(); q.pop(); v[u.x][u.y]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(canarrive[u.x][u.y][i][j]) { if(i==ed.x&&j==ed.y) { if(f[u.x][u.y]<f[i][j]) { f[i][j]=f[u.x][u.y]; num[i][j]=num[u.x][u.y]; }else if(f[u.x][u.y]==f[i][j]) { num[i][j]+=num[u.x][u.y]; } }else { if(f[u.x][u.y]+1<f[i][j]) { f[i][j]=f[u.x][u.y]+1; num[i][j]=num[u.x][u.y]; if(!v[i][j]) { v[i][j]=1; point tmp; tmp.x=i,tmp.y=j; q.push(tmp); } }else if(f[u.x][u.y]+1==f[i][j]) { num[i][j]+=num[u.x][u.y]; if(!v[i][j]) { v[i][j]=1; point tmp; tmp.x=i,tmp.y=j; q.push(tmp); } } } } } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&map[i][j]); if(map[i][j]==3)st.x=i,st.y=j; else if(map[i][j]==4)ed.x=i,ed.y=j; } } floodfill(st.x,st.y); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!map[i][j])floodfill(i,j); } } memset(f,0x3f,sizeof(f)); bfs(); if(f[ed.x][ed.y]==0x3f3f3f3f)printf("-1\n"); else { printf("%d\n",f[ed.x][ed.y]); printf("%lld\n",num[ed.x][ed.y]); } return 0; }
- 1
信息
- ID
- 1698
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 3
- 已通过
- 3
- 上传者