2 solutions

  • 1
    @ 2024-8-12 10:36:52
    #include<bits/stdc++.h>
    using namespace std;
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};
    const int N=110;
    char g[N][N];
    bool st[N][N];
    int sx,sy,ex,ey;
    int n,m;
    bool dfs(int x,int y)
    {
    	st[x][y]=1;
    	if(x==ex&&y==ey)
    	{
    		return true;
    	}
    	for(int i=0;i<4;i++)
    	{
    		int a=x+dx[i],b=y+dy[i];
    		if(a<0||a>=n||b<0||b>=m)
    		{
    			continue;
    		}
    		if(g[a][b]=='#')
    		{
    			continue;
    		}
    		if(st[a][b]==1)
    		{
    			continue;
    		}
    		if(dfs(a,b)==true)
    		{
    			return true;
    		}
    	}
    	return false;
    }
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		cin>>n;
    		m=n;
    		memset(st,0,sizeof st);
    		for(int i=0;i<n;i++)
    		{
    			cin>>g[i];
    		}
    		cin>>sx>>sy>>ex>>ey;
    		if(g[sx][sy]=='#')
    		{
    			cout<<"NO"<<endl;
    		}
    		else
    		{
    			if(dfs(sx,sy)==true)
    			{
    				cout<<"YES"<<endl;
    			}
    			else
    			{
    				cout<<"NO"<<endl;
    			}
    		}
    	}
    	return 0;
    }
    
    • -1
      @ 2024-8-12 10:22:17
      #include<bits/stdc++.h>
      using namespace std;
      const int N=110;
      char g[N][N];
      bool st[N][N];
      int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
      int sx,sy,ex,ey;
      int n,m;
      bool dfs(int x,int y)
      {
          st[x][y]=1;
          if(x==ex&&y==ey)
          {
              return true;
          }
          for(int i=0;i<4;i++)
          {
              int a=x+dx[i],b=y+dy[i];
              if(a<0||a>=n||b<0||b>=m) continue;
              if(g[a][b]=='#') continue;
              if(st[a][b]) continue;
              if(dfs(a,b)) return true;
          }
          return false;
      }
      int main()
      {
          int t;
          cin>>t;
          while(t--)
          {
              cin>>n;
              m=n;
              memset(st,0,sizeof st);
              for(int i=0;i<n;i++) cin>>g[i];
              cin>>sx>>sy>>ex>>ey;
              if(g[sx][sy]=='#') cout<<"NO"<<endl;
              else
              {
                  if(dfs(sx,sy)) cout<<"YES"<<endl;
                  else cout<<"NO"<<endl;
              }
          }
          return 0;
      }
      
      • 1

      Information

      ID
      1010
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      3
      Tags
      (None)
      # Submissions
      11
      Accepted
      4
      Uploaded By