Untitled
unknown
plain_text
2 years ago
1.3 kB
2
Indexable
#include<iostream> using namespace std; int q_x[100000]; int q_y[100000]; int bot=-1; int top=-1; void push(int i,int j) { bot++; q_x[bot]=i; q_y[bot]=j; } void pop(){top++;} bool is_emty(){return top==bot;} //----------------------------------- int n,m; char a[300][300]; int vis[300][300]; int dx[4]={0,-1,0,1}; int dy[4]={-1,0,1,0}; int x_start,y_start,x_end,y_end; void BFS() { top=bot=-1; push(x_start,y_start); vis[x_start][y_start]=-1; while(!is_emty()) { int f1 = q_x[top+1]; int f2 = q_y[top+1]; pop(); for(int k=0;k<4;k++) { int i1 =f1; int j1 = f2; while (true) { i1 += dx[k]; j1 += dy[k]; if(a[i1][j1]=='1' || i1<1 ||i1>n ||j1<1||j1>m) break; if(vis[i1][j1]==-1) { vis[i1][j1]=vis[f1][f2]+1; push(i1,j1); } else if(vis[i1][j1]>vis[f1][f2]+1) { vis[i1][j1]=vis[f1][f2]+1; push(i1,j1); } } } } } int main() { int T; cin>>T; for(int tc=1;tc<=T;tc++) { cin>>m>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { vis[i][j]=-1; } } cin>>y_start>>x_start>>y_end>>x_end; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } BFS(); cout<<vis[x_end][y_end]<<endl; } return 0; }
Editor is loading...