Untitled
unknown
plain_text
2 years ago
1.3 kB
3
Indexable
#include <iostream> #define N 505 using namespace std; int n,m; int a[N][N]; int cnt; int stx,sty,fx,fy; bool ans; int hx[]={0,-1,0,1}; int hy[]={-1,0,1,0}; int dd[N][N]; int sx[N]; int sy[N]; int dau,cuoi; bool bfs(int x,int y) { dau=1; cuoi=0; //cout<<x<<" "<<y<<" "<<a[x][y]<<"\n"; //if(a[x][y]==1) { sx[++cuoi]=x; sy[cuoi]=y; } while(dau<=cuoi) { int u=sx[dau]; int v=sy[dau]; dau++; for(int i=0;i<4;i++) { int xx=u+hx[i]; int yy=v+hy[i]; if(xx>0&&xx<=n&&yy>0&&yy<=m) { if(xx==fx&&yy==fy) { if(a[xx][yy]==0)return true;else { a[xx][yy]=0; sx[++cuoi]=xx; sy[cuoi]=yy; } }else if(a[xx][yy]==1&&dd[xx][yy]==0) { dd[xx][yy]=1; sx[++cuoi]=xx; sy[cuoi]=yy; } } } } return false; } void doc() { ans=true; cnt=0; cin>>n>>m; cin>>stx>>sty>>fx>>fy; stx++; sty++; fx++; fy++; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; dd[i][j]=0; } ans=bfs(stx,sty); if(ans)cout<<"YES\n";else cout<<"NO\n"; } int TC; int main() { //freopen("input.txt","r",stdin); cin>>TC; for(int tc=1;tc<=TC;tc++) { //cout<<TC<<"\n"; doc(); } return 0; }
Editor is loading...