2 条题解

  • 1

    dfs版:

    #include <iostream>
    #include <cstring> 
    using namespace std;
    struct point{
    	int x,y;
    }; 
    point s,t;
    int n;
    char a[110][110];
    bool vis[110][110];
    bool flag=false;
    int d[][2]={{-1,0},{1,0},{0,-1},{0,1}};
    void dfs(point p){
    	if(p.x==t.x&&p.y==t.y){
    		flag=true;
    		return;
    	}
    	for(int i=0;i<4;i++){
    		point nxt;
    		nxt.x=p.x+d[i][0];
    		nxt.y=p.y+d[i][1];
    		if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>n)continue;
    		if(a[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y]){
    			vis[nxt.x][nxt.y]=1;
    			dfs(nxt);
    		}
    	}
    } 
    int main(){
    	int T;
    	cin>>T;
    	while(T--){
    		cin>>n;
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				cin>>a[i][j];
    			}
    		}
    		cin>>s.x>>s.y>>t.x>>t.y;
    		s.x++;s.y++;t.x++;t.y++;
    		flag=false;
    		memset(vis,0,sizeof vis);
    		vis[s.x][s.y]=1;
    		dfs(s);
    		if(flag)cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
    }
    

    bfs版:

    #include <iostream>
    #include <cstring> 
    #include <queue>
    using namespace std;
    struct point{
    	int x,y;
    }; 
    point s,t;
    int n;
    char a[110][110];
    bool vis[110][110];
    bool flag=false;
    int d[][2]={{-1,0},{1,0},{0,-1},{0,1}};
    void bfs(point s){
    	queue<point>q;
    	q.push(s);
    	vis[s.x][s.y]=1;
    	while(!q.empty()){
    		point p=q.front();
    		q.pop();
    		if(p.x==t.x&&p.y==t.y){
    			flag=true;
    			return;
    		}
    		for(int i=0;i<4;i++){
    			point nxt;
    			nxt.x=p.x+d[i][0];
    			nxt.y=p.y+d[i][1];
    			if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>n)continue;
    			if(a[nxt.x][nxt.y]=='.'&&!vis[nxt.x][nxt.y]){
    				vis[nxt.x][nxt.y]=1;
    				q.push(nxt);
    			}
    		}
    	}
    
    } 
    int main(){
    	int T;
    	cin>>T;
    	while(T--){
    		cin>>n;
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				cin>>a[i][j];
    			}
    		}
    		cin>>s.x>>s.y>>t.x>>t.y;
    		s.x++;s.y++;t.x++;t.y++;
    		flag=false;
    		memset(vis,0,sizeof vis);
    		vis[s.x][s.y]=1;
    		bfs(s);
    		if(flag)cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
    }
    
    • 0
      @ 2024-7-19 11:47:22
      #include<iostream>
      #include<cstring>
      using namespace std;
      const int N=1e3+520;
      int n,t,sx,sy,ex,ey;
      char a[N][N];
      int dx[]={0,0,1,-1};
      int dy[]={1,-1,0,0};
      bool flag;
      bool check(int x,int y){
      	if(x>=0&&x<n&&y>=0&&y<n&&a[x][y]=='.')
      		return 1;
      		
      	return 0;
      }
      void dfs(int x,int y){
      	if(x==ex&&y==ey){
      		flag=1;
      		return ;
      	}
      	for(int i=0;i<=3;i++){
      		int xx=x+dx[i];
      		int yy=y+dy[i];
      		if(check(xx,yy)){
      			a[xx][yy]='#';
      			dfs(xx,yy);
      		}
      	}
      }
      int main(){
      	cin>>t;
      	while(t--){
      		cin>>n;
      		for(int i=0;i<n;i++){
      			for(int j=0;j<n;j++){
      				cin>>a[i][j];
      			}
      		}
      		cin>>sx>>sy>>ex>>ey;
      		dfs(sx,sy);
      		if(flag){
      			cout<<"YES"<<endl;
      		}else{
      			cout<<"NO"<<endl;
      		}
      		flag=0;
      	}
      	return 0;
      }
      
      • 1

      信息

      ID
      3023
      时间
      1000ms
      内存
      256MiB
      难度
      4
      标签
      递交数
      48
      已通过
      23
      上传者