贪吃蛇迷宫80分求助

问题讨论区 提高段
1

题目描述


image

问题

TLE 80

代码

#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;
bool ans = 0;
char c[5] = {'s', 'n', 'u', 'k', 'e'};
int n, m;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
vector<vector<bool>> vis;
vector<vector<char>> mp;
bool dfs(int x, int y, int idx)
{
    if (x == n && y == m)
    {
        return 1;
    }
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx > n || ty > m)
            continue;
        if (vis[tx][ty])
            continue;
        if (mp[tx][ty] != c[(idx + 1) % 5])
            continue;
        vis[tx][ty] = 1;
        if (dfs(tx, ty, (idx + 1) % 5))
            return 1;
        vis[tx][ty] = 0;
    }
    return 0;
}
int main()
{
    cin >> n >> m;
    mp.resize(n + 1, vector<char>(m + 1));
    vis.resize(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    cout << (dfs(1, 1, 0) ? "Yes" : "No");
    return 0;
}
2

@CZF2919 救一下

3

https://discourse.xinyoudui.com/t/topic/39380/23

4

你是不是没判断起点？？

5

@杨北辰 @杨北辰
若起点不是“s",直接输出‘No’

6

<think>em…</think>

7 
#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;
bool ans = 0;
char c[5] = {'s', 'n', 'u', 'k', 'e'};
int n, m;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
vector<vector<bool>> vis;
vector<vector<char>> mp;
bool dfs(int x, int y, int idx)
{
    if (mp[x][y] != c[idx])
        return 0;
    if (x == n && y == m)
    {
        return 1;
    }
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx > n || ty > m)
            continue;
        if (vis[tx][ty])
            continue;
        vis[tx][ty] = 1;
        if (dfs(tx, ty, (idx + 1) % 5))
            return 1;
        vis[tx][ty] = 0;
    }
    return 0;
}
int main()
{
    cin >> n >> m;
    mp.resize(n + 1, vector<char>(m + 1));
    vis.resize(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    cout << (dfs(1, 1, 0) ? "Yes" : "No");
    return 0;
}
/*
2 3
sns
euk

2 2
ab
cd

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku
*/

还是不对 TLE80

8

这TLE？？

9

en

10

你的vis[1][1]=1

11

你起点没初始化

12

我说了

13

然后对于snuke的判断不对

14

image

15

为什么是对新的x,y判断

16

我的step从0开始

17

你再改一下，应该就好了

18
code 
#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;
bool ans = 0;
char c[5] = {'s', 'n', 'u', 'k', 'e'};
int n, m;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
vector<vector<bool>> vis;
vector<vector<char>> mp;
bool dfs(int x, int y, int idx)
{
    vis[x][y] = 1;
    if (mp[x][y] != c[idx])
        return 0;
    if (x == n && y == m)
    {
        return 1;
    }
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx > n || ty > m)
            continue;
        if (vis[tx][ty])
            continue;
        if (dfs(tx, ty, (idx + 1) % 5))
            return 1;
        vis[tx][ty] = 0;
    }
    return 0;
}
int main()
{
    cin >> n >> m;
    mp.resize(n + 1, vector<char>(m + 1));
    vis.resize(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    cout << (dfs(1, 1, 0) ? "Yes" : "No");
    return 0;
}
/*
2 3
sns
euk

2 2
ab
cd

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku
*/
19

哦哦

20

A了么