VictorTang @ 2024-01-30 20:56:47
AtCoder Beginner Contest 176_D 原题题面
AC x 4
WA x 10
Help!
（DFS为何不行?)
附上代码
#include<iostream>
#define INF 99999999
typedef long long LL;
using namespace std;
LL n, m, s, t, u, v;
char mp[1003][1003];
bool visit[1003][1003];
LL dx[] = {0, 0, -1, 1};
LL dy[] = {-1, 1, 0, 0};
LL solve(LL x, LL y){
if (x == u and y == v)
return 0;
visit[x][y] = true;
LL ret = INF;
for (LL d=0; d<n; d++){
LL newX = dx[d] + x;
LL newY = dy[d] + y;
if (newX < 1 or newX > n
or newY < 1 or newY > m) continue;
if (!visit[newX][newY] and mp[newX][newY] == '.') ret = min(ret, solve(newX, newY));
}
for (LL i=x-2; i<=x+2; i++){
for (LL j=y-2; j<=y+2; j++){
if (i < 1 or i > n
or j < 1 or j > m) continue;
if (!visit[i][j] and mp[i][j] == '.') ret = min(ret, solve(i, j)+1);
}
}
return ret;
}
int main(){
cin >> n >> m
>> s >> t
>> u >> v;
for (LL i=1; i<=n; i++)
for (LL j=1; j<=m; j++)
cin >> mp[i][j];
LL ans = solve(s, t);
if (ans == INF) cout << -1;
else cout << ans;
}by lihongqian__int128 @ 2024-02-11 19:42:07
@VictorTang
for (LL d=0; d<n; d++) 是啥意思？？？
不应该是
for (LL d=0; d<4; d++)
吗?
by VictorTang @ 2024-07-14 15:09:03
@lihongqian__int128
#include<iostream>
#define INF (1LL << 60)
typedef long long LL;
using namespace std;
LL n, m, s, t, u, v;
char mp[1003][1003];
bool visit[1003][1003];
LL dx[] = {0, 0, -1, 1};
LL dy[] = {-1, 1, 0, 0};
LL solve(LL x, LL y){
if (x == u and y == v)
return 0;
visit[x][y] = true;
LL ret = INF;
for (LL d=0; d<4; d++){
LL newX = dx[d] + x;
LL newY = dy[d] + y;
if (newX < 1 or newX > n
or newY < 1 or newY > m) continue;
if (!visit[newX][newY] and mp[newX][newY] == '.') ret = min(ret, solve(newX, newY));
}
for (LL i=x-2; i<=x+2; i++){
for (LL j=y-2; j<=y+2; j++){
if (i < 1 or i > n
or j < 1 or j > m) continue;
if (!visit[i][j] and mp[i][j] == '.') ret = min(ret, solve(i, j)+1);
}
}
return ret;
}
int main(){
cin >> n >> m
>> s >> t
>> u >> v;
for (LL i=1; i<=n; i++)
for (LL j=1; j<=m; j++)
cin >> mp[i][j];
LL ans = solve(s, t);
if (ans == INF) cout << -1;
else cout << ans;
}