时间能过，O(n^2)的
（每个地方最多被走一次）
by llycdasanbing @ 2022-07-29 15:35:03
@[llycdasanbing](/user/495908)
您不能过的数据：
```
5
00000
00000
11110
11110
11110
1 1 5 5
```
您的输出：```12```
应该输出：```8```
~~手捏的~~
by coldy_rainy @ 2022-07-29 16:03:17
@[llycdasanbing](/user/495908)
这是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 coldy_rainy @ 2022-07-29 16:37:19
@[penhaochen](/user/526755) 感谢大佬，我接着优化去了
by llycdasanbing @ 2022-07-29 19:21:17