Untitled
unknown
plain_text
5 months ago
1.9 kB
1
Indexable
Never
#include <iostream> #define N 201 #define oo 2000000009 using namespace std; int min(int u, int v) { if(u>v)return v; return u; } int max(int u, int v) { if(u>v)return u; return v; } int n,m; int sr,sc,fr,fc; char a[N][N]; int sx[N*N],sy[N*N],sz[N*N]; int hx[]={0,-1,0,1}; int hy[]={-1,0,1,0}; int dd[N][N][5]; void doc() { cin>>m>>n; cin>>sc>>sr>>fc>>fr; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; for(int l=0;l<4;l++)dd[i][j][l]=0; } } void bfs(int u,int v) { int dau=1; int cuoi=0; for(int i=0;i<4;i++) { int xx=u,yy=v,zz=i; do { dd[xx][yy][zz]=1; sx[++cuoi]=xx; sy[cuoi]=yy; sz[cuoi]=zz; xx=xx+hx[zz]; yy=yy+hy[zz]; }while(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0'); } while(dau<=cuoi) { int x=sx[dau]; int y=sy[dau]; int z=sz[dau]; //cout<<x<<" "<<y<<" "<<z<<" "<<dd[x][y][z]<<"\n"; dau++; int xx=x,yy=y,zz=z; do { xx=xx+hx[z]; yy=yy+hy[z]; if(xx>0&&xx<=n&&yy>0&&yy<=m&&dd[xx][yy][z]==0&&a[xx][yy]=='0') { dd[xx][yy][zz]=dd[x][y][z]; sx[++cuoi]=xx; sy[cuoi]=yy; sz[cuoi]=zz; } }while(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0'); for(int i=0;i<4;i++)if(i!=z) { xx=x+hx[i]; yy=y+hy[i]; zz=i; int cp=1; if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0') { if(dd[xx][yy][zz]==0) { dd[xx][yy][zz]=dd[x][y][z]+cp; sx[++cuoi]=xx; sy[cuoi]=yy; sz[cuoi]=zz; }else if(dd[xx][yy][zz]>dd[x][y][z]+cp)dd[xx][yy][zz]=dd[x][y][z]+cp; } } } } int main() { //freopen("input.txt","r",stdin); int TC; cin>>TC; for(int tc =1;tc<=TC;tc++) { int ans=oo; doc(); bfs(sr,sc); for(int i=0;i<4;i++)if(dd[fr][fc][i])ans=min(ans,dd[fr][fc][i]-1); if(ans==oo)ans=-1; cout<<ans<<"\n"; } return 0; }