传送门

其实题本身模型不难，打的时候被一个不知道的细节坑了

但是场上只有879/21436过了这题，稍微有点奇怪

一句话题意

给定n×mn\times m网格，网格上有障碍（用"#“表示）和一个终点（用"L"表示），非障碍格用”."表示。

现网格上有一个机器人，可以对其下达向上、下、左、右移动一格的指令。但该机器人会向与指令方向相异且非障碍的方向移动，若移动不了则原地不动。

求棋盘上有哪些位置满足当机器人位于该位置时，只要给出一定的操作序列，一定能使机器人到达终点。在棋盘上将这些点标为"+"。

n,m≤106n,m\le 10^6

∑nm≤106\sum nm\le 10^6

题解

其实很简单。从终点出发开始扩展，考虑检验当前格子是否可行。如果当前格子的相邻格子中只有一个是".“（换言之，其他都是”+“或”#“），那么这个格子就是可行的，因为我们可以下达让机器人移动到”."的指令，来让它到达一个可行点，从而可以使其一直向终点移动。

若当前点可行，将当前点标记为"+“，那么可以继续检验与当前点相邻的”."是否可行，否则停止当前格子的扩展。

时间复杂度O(∑nm)O(\sum nm)

坑在哪

想法其实是没问题的，复杂度也正确，问题在于n,m≤106n,m\le 10^6，于是我索性用了vector<string>来根据每一组数据开不同大小的表格。

然后就想当然地使用cout来输出，并且非常自信地使用了

1
endl

提交

TLE

？？？

然后就

寄

怎么会事呢？

赛后@Candy Ore大佬看了眼16号点，发现是一个1e6×11e6\times 1​的数据，并向我科普了使用endl和\n进行换行的区别糖矿大佬好像也是死于此。

总之大概是这个样子

endlvsn

图源

改完之后就A了

囸

属于是学艺不精了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn=1000000+100;
int T;
int n,m;
int lx,ly;
int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int vst[maxn];

void DFS(int x,int y,vector<string> &a)
{
    if(x<0 || x>=n || y<0 || y>=m || a[x][y]=='#' || a[x][y]=='+')
        return;
    vst[x*m+y]=1;
    int cnt=0;
    int nx,ny;
    for(int i=0;i<4;++i)
    {
        int X=x+dx[i],Y=y+dy[i];
        if(X<0 || X>=n || Y<0 || Y>=m || a[X][Y]=='#')
            continue;
        if(a[X][Y]!='+')
        {
            nx=X,ny=Y;
            ++cnt;
        }
    }
    if(cnt>1)
        return;
    a[x][y]='+';
    if(cnt==1)
        DFS(nx,ny,a);
}

void Work()
{
    cin>>n>>m;
    vector<string> a(n);
    for(int i=0;i<n;++i)
        cin>>a[i];
    lx=-1,ly=-1;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            vst[i*m+j]=0;
    for(int i=0;i<n && lx==-1;++i)
        for(int j=0;j<m && lx==-1;++j)
            if(a[i][j]=='L')
            {
                lx=i,ly=j;
                a[i][j]='+';
                vst[i*m+j]=1;
                break;
            }
    for(int i=0;i<4;++i)
    {
        int X=lx+dx[i],Y=ly+dy[i];
        if(X>=0 && X<n && Y>=0 && Y<m && a[X][Y]!='#')
            DFS(X,Y,a);
    }
    a[lx][ly]='L';
    for(int i=0;i<n;++i)
        cout<<a[i]<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        Work();
    }
    return 0;
}