C. Pipes

Codeforces Round #590 (Div. 3)

题目链接:https://codeforces.com/contest/1234/problem/C

题目描述:

题目

思路:

大概就是,说是六种水管,实质上是两种,12是一种,3456是一种(因为它们都可以任意旋转)。我们从起点出发,根据当前水管的类型以及它所在的位置和上一步所在的位置,结合目标位置的,设计水流的前进方。如果能够到达目标位置则输出yes,如果在水流的过程中超出了两行n列水管的范围,则水流不能到达目标位置。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<map>
using namespace std;
int q,n;
const int maxn=2e5+5;
char a[5][maxn];
int dfs(int x,int y,int l){
    int nx,ny;
    if(x==2&&y==n) return 1;
    if(x<1||y<0||x>2||y>=n)return 0;
 
    if(a[x][y]=='1'||a[x][y]=='2'){
        if(l==x){
            nx=x;
            ny=y+1;
            dfs(nx,ny,x);
        }
        else return 0;
 
    }
    else if(a[x][y]=='3'||a[x][y]=='4'||a[x][y]=='5'||a[x][y]=='6'){
        if(l==1&&x==1){
            nx=x+1;
            ny=y;
        }
        else if(l==1&&x==2){
            nx=x;
            ny=y+1;
        }
        else if(l==2&&x==1){
            nx=x;
            ny=y+1;
        }
        else if(l==2&&x==2){
            nx=x-1;
            ny=y;
        }
        else return 0;
        dfs(nx,ny,x);
    }
}
 
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&q);
    while(q--){
 
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=2;i++){
            scanf("%s",a[i]);
        }
        if(dfs(1,0,1)==1){
            printf("YES\n");
        }
        else printf("NO\n");
 
    }
    return 0;
}
Last modification:December 15th, 2019 at 12:30 am
如果觉得我的文章对你有用,请随意赞赏