题解
2023-07-06 13:49:16
发布于:上海
235阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 2e9;
int sx, sy, fx, fy;
bool visit[49][49];
char MAP[49][49];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool TF(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y, int sum)
{
if(x == fx && y == fy)
{
if(sum < ans)
{
ans = sum;
}
return;
}
visit[x][y] = 1;
for(int i = 0; i < 4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(TF(nx, ny) && ! visit[nx][ny] && MAP[nx][ny] != '#')
{
if(MAP[nx][ny] >= '1' && MAP[nx][ny] <= '9')
{
dfs(nx, ny, sum + (MAP[nx][ny] - '0') + 1);
}
else
{
dfs(nx, ny, sum + 1);
}
}
}
visit[x][y] = false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> MAP[i][j];
if(MAP[i][j] == 'Z')
{
sx = i, sy = j;
}
if(MAP[i][j] == 'W')
{
fx = i, fy = j;
}
}
}
dfs(sx, sy, 0);
if(ans == 2e9)
{
cout << "IMPOSSIBLE";
}
else
{
cout << ans;
}
return 0;
}
全部评论 1
头像好品味
2023-07-27 来自 浙江
0谢谢
2023-07-27 来自 上海
0我朋友有一个和你一模一样的头像
2023-08-17 来自 浙江
0谁呀?我咋不知道?
2023-08-17 来自 浙江
0
有帮助,赞一个