求助，样例过了手写大数据也过了

P1746 离开中山路

llycdasanbing @ 2022-07-29 15:33:00

#include<bits/stdc++.h>
using namespace std;
int dx[5] {0, 1, -1, 0, 0};
int dy[5] {0, 0, 0, 1, -1};
int mapp[1005][1005];
int n, desx, desy;
const int inf = 2147483647;
bool vis[1005][1005];
char der[5] {'\0', 'd', 'u', 'r', 'l'};
int dfs(int x, int y) {
    int ret = inf;
    if (mapp[x][y]) {
    //  printf("(%d,%d)是死路，不能走\n",x,y);
        return inf;   //走回头路或者到店铺就惩罚
    }
    if(vis[x][y])return inf; 
    vis[x][y]=1;
    if (desx == x && desy == y)return 0; //到终点就返回0
    for (int i = 1; i <= 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
            continue; //越界就下一个
        }
        int now=dfs(nx,ny);
        ret = min(now, ret); //求四个的最小值
    //  if(now!=inf)printf("从(%d,%d)向%c走到(%d,%d)\n", x, y, der[i], nx, ny);
    }
    if (ret == inf)return inf; //自己是思路&四个方向全是死路就惩罚
    return ret + 1; //返回下一步的最小值+自己

}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++)
            mapp[i][j] = s[j - 1] - '0';
    }
    int sx, sy;
    cin >> sx >> sy >> desx >> desy;
    cout << dfs(sx, sy);
}

或者谁能给一个我这个程序过不了的数据（这个洛谷他不到点不给我获取次数）

谢谢各位大佬

by llycdasanbing @ 2022-07-29 15:35:03

时间能过，O(n^2)的

（每个地方最多被走一次）

by coldy_rainy @ 2022-07-29 16:03:17

@llycdasanbing

您不能过的数据：

您的输出：12

应该输出：8

~~手捏的~~

by coldy_rainy @ 2022-07-29 16:37:19

@llycdasanbing

这是DFS的修改版，#4AC,其他TLE。不过可以过我那个~~手捏的烂~~数据：

#include<bits/stdc++.h>
using namespace std;
int dx[5] {0, 1, -1, 0, 0};
int dy[5] {0, 0, 0, 1, -1};
int mapp[1005][1005];
int n, desx, desy;
const int inf = 2147483647;
bool vis[1005][1005];
char der[5] {'\0', 'd', 'u', 'r', 'l'};
int dfs(int x, int y) {
    int ret = inf;
    if (mapp[x][y]) {
      //printf("(%d,%d)是死路，不能走\n",x,y);
        return inf;   //走回头路或者到店铺就惩罚
    }
    //if(vis[x][y])return inf;/*删*/
    //vis[x][y]=1;/*删*/
    if (desx == x && desy == y)return 0; //到终点就返回0
    for (int i = 1; i <= 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx <= 0 || nx > n || ny <= 0 || ny > n||vis[nx][ny]/*加*/) {
            continue; //越界就下一个
        }
        vis[nx][ny]=1;/*加*/
        int now=dfs(nx,ny);
        vis[nx][ny]=0;/*加*/
        ret = min(now, ret); //求四个的最小值
        //if(now!=inf)printf("从(%d,%d)向%c走到(%d,%d)\n", x, y, der[i], nx, ny);
    }
    if (ret == inf)return inf; //自己是思路&四个方向全是死路就惩罚
    return ret + 1; //返回下一步的最小值+自己

}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++)
            mapp[i][j] = s[j - 1] - '0';
    }
    int sx, sy;
    cin >> sx >> sy >> desx >> desy;
    cout << dfs(sx, sy);
}

原因：DFS搜索要回溯，因此之前的vis状态在下一次搜索后要回归于0.

by llycdasanbing @ 2022-07-29 19:21:17

@penhaochen 感谢大佬，我接着优化去了