C++14(g++5.4) 解法, 执行用时: 132ms, 内存消耗: 620K, 提交时间: 2020-05-25 17:55:09

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 10100;

int t, n, m;
char a[N][N];
struct Node {
    int v, nxt;
}edge[M * 3];

int cnt, head[M];
bool vis[M];

void init()
{
    cnt = 0;
    memset(head, -1, sizeof head);
    memset(vis, false, sizeof vis);
}
void add(int x, int y)
{
  //  cout << x/m << ' ' <<x%m << ' ' << y /m<<' ' << y%m<<endl;
    edge[cnt].v = y; edge[cnt].nxt = head[x]; head[x] = cnt++;
    edge[cnt].v = x; edge[cnt].nxt = head[y]; head[y] = cnt++;
}
bool bfs()
{
    queue<int> que;
    for(int i = 0; i < m; i++) que.push(i), vis[i] = true;

    while(!que.empty()) {
        int h = que.front(); que.pop();

        if(h >= n * m) return true;

        for(int i = head[h], v; ~i; i = edge[i].nxt) {
            v = edge[i].v;
            if(!vis[v]) {
                vis[v] = true;
                que.push(v);
            }
        }
    }

    return false;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    scanf("%d", &t);

    bool ans;
    while(t--) {
        init();

        scanf("%d%d", &n, &m);

        for(int i = 0; i < n; i++) {
            scanf("%s", a[i]);
        }

        for(int i = 0; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(a[i][j] == 'L') {
                    if(a[i][j-1] == 'L') add(i*m+j, (i+1)*m+j-1);
                    else add(i*m+j, i*m+j-1);
                }
                else {
                    if(a[i][j-1] == 'L') add((i+1)*m+j, (i+1)*m+j-1);
                    else add(i*m+j-1, (i+1)*m+j);
                }
            }
        }

        if(bfs()) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 907ms, 内存消耗: 2136K, 提交时间: 2019-05-09 21:09:18

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[510][510];
char ch[110];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dfs(int x,int y){
    if(a[x][y]||x<1||x>n||y<1||y>m) return 0;
    if(x==n) return 1;
    a[x][y]=1;
    for(int i=0;i<4;i++) if(dfs(x+dx[i],y+dy[i])) return 1;
    return 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%s",ch+1);
            for(int j=1;j<=m;j++){
                if(ch[j]=='L') a[i*5-4][j*5]=a[i*5-3][j*5-1]=a[i*5-2][j*5-2]=a[i*5-1][j*5-3]=a[i*5][j*5-4]=1;
                if(ch[j]=='R') a[i*5-4][j*5-4]=a[i*5-3][j*5-3]=a[i*5-2][j*5-2]=a[i*5-1][j*5-1]=a[i*5][j*5]=1;
            }
        }
        n*=5,m*=5;
        int bl=0;
        for(int i=1;i<=m;i++){
            if(dfs(1,i)){
                printf("Yes\n");
                bl=1;
                break;
            }
        }
        if(!bl) printf("No\n");
    }
    return 0;
}