CF-Tinkoff Challenge-Elimination Round-B-Igor and his way to work

描述

题解

这个题很简单的一个 dfs 题，但是我因为写习惯了二维标记的 dfs，忽然写这个没反应过来，花式 WA 与 TLE，不加标记记忆化 TLE，加标记记忆化就 WA，最后无奈放弃了。

如果不是 dfs 写着不顺，我也不会想起更好的方法，所以，这不想了一个划十字的方法，首先我们考虑一下，凡是满足题意的路径走法有几种，经过思考，一共三种分为两类。

第一类，转一次弯或者不转弯，转一次弯，说明分别从起点和终点出发沿着一条直线走会相交，不转弯说明起点和终点在同一条直线上且可直达，这个可以考虑为我们分别从起点和终点画十字，如果出现相交，则 YES。

第二类，也就是转两次弯，这个情况稍微麻烦一些，因为我们知道，如果分别从起点、终点画十字却没有相交，那么他们想要能够抵达终点，必须存在一条直线段可以讲这两个十字进行连接，那么我们只要找到这个可行解就 YES。

最后如果都没有输出 YES，就一定是 NO 了。第一类过程的复杂度是 O(m+n) ，第二类过程的复杂度则是 O(m∗n) ，所以总体来说，效果应该比 dfs 好一些。

后来经过思考，发现我之所以 dfs TLE 是因为没有标记，而 WA 是因为标记错误，那么标记为什么错了呢？想来想去，发现这个需要用三维标记，因为每一个点我们还需要对其每一个方向进行最少转弯次数的标记，同样是一个点，向不同方向转弯可能最少转弯次数并不一样。

大致就是这样，发现做题不能太固执，让思维僵化了就 GG 了！！！

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1010;
const int dir[4][2] = {
  {
  0, 1}, {
  0, -1}, {
  1, 0}, {-1, 0}};   // 右，左，下，上

int n, m;
int flag = 0;
char s[MAXN][MAXN];
int vis[MAXN][MAXN];
int sx, sy, tx, ty;

int main(int argc, const char * argv[])
{
    memset(vis, 0, sizeof(vis));

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        scanf("%s", s[i]);
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == 'S')
            {
                sx = i;
                sy = j;
                vis[sx][sy] = 1;
            }
            else if (s[i][j] == 'T')
            {
                tx = i;
                ty = j;
            }
        }
    }

    int x, y;
    for (int i = 0; i < 4; i++)
    {
        x = sx + dir[i][0];
        y = sy + dir[i][1];
        while (0 <= x && x < n && 0 <= y && y < m && s[x][y] != '*')
        {
            vis[x][y] = 1;
            x += dir[i][0];
            y += dir[i][1];
        }
    }
    if (vis[tx][ty])
    {
        cout << "YES\n";
        return 0;
    }

// for (int i = 0; i < n; i++)
// {
   
// for (int j = 0; j < m; j++)
// {
   
// cout << vis[i][j];
// }
// cout << endl;
// }

    for (int i = 0; i < 4; i++)
    {
        x = tx + dir[i][0];
        y = ty + dir[i][1];
        while (0 <= x && x < n && 0 <= y && y < m && s[x][y] != '*')
        {
            if (vis[x][y])
            {
                cout << "YES\n";
                return 0;
            }
            int j = i < 2 ? 2 : 0;
            int x_ = x + dir[j][0];
            int y_ = y + dir[j][1];
            while (0 <= x_ && x_ < n && 0 <= y_ && y_ < m && s[x_][y_] != '*')
            {
                if (vis[x_][y_])
                {
                    cout << "YES\n";
                    return 0;
                }
                x_ += dir[j][0];
                y_ += dir[j][1];
            }
            j++;
            x_ = x + dir[j][0];
            y_ = y + dir[j][1];
            while (0 <= x_ && x_ < n && 0 <= y_ && y_ < m && s[x_][y_] != '*')
            {
                if (vis[x_][y_])
                {
                    cout << "YES\n";
                    return 0;
                }
                x_ += dir[j][0];
                y_ += dir[j][1];
            }
            x += dir[i][0];
            y += dir[i][1];
        }
    }

    cout << "NO\n";

    return 0;
}