题目链接：https://codeforces.com/contest/1234/problem/C
思路：这个题似乎还有不dp的办法，这次先把dp的方法放在这里，因为只有两行，所以水不能往左走，不然水管会交叉。用dp[i][j][0] ， dp[i][j][1] , dp[i][j][2]表示水能否从i行j列的从左、从上、从下流入管道(i,j)，即可写出状态转移方程。
代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int dp[2][maxn][3]; int main() { int q; ios::sync_with_stdio(0); cin >> q; while(q--) { int n; memset(dp , 0 , sizeof(dp)); cin >> n; string s[2]; cin >> s[0] >> s[1]; int len = s[0].length(); dp[0][0][0] = 1; for(int j = 0 ; j < len ; j++) { for(int i = 0 ; i < 3 ; i++) { int t = i % 2; if(s[t][j] - '0' <= 2 ) { dp[t][j + 1][0] |= dp[t][j][0]; } else { if(t == 1) dp[t - 1][j][1] |= dp[t][j][0]; if(j < len) dp[t][j + 1][0] |= dp[t][j][2] | dp[t][j][1]; if(t == 0) dp[t + 1][j][2] |= dp[t][j][0]; } } } if(dp[1][len][0])cout << "YES\n"; else cout << "NO\n"; } return 0; }