小豆子范德萨 @ 2020-04-21 14:27:28
调了半天BUG了做不出来、帮下呀
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int broke[310][310]; //broke[i][j] = i代表需要在i之前到达才可以(i都不行)
bool vis[310][310];
int ans = 1e9;
int dir[4][2] = {
{-1,0},
{1,0},
{0,-1},
{0,1}
};
bool inside(int x,int y) {
if(x < 0 || y < 0) return false;
return true;
}
void dfs(int x,int y,int time) {
if(time >= ans || broke[x][y] <= time) return;
if(broke[x][y] == 1e9) {
ans = min(ans,time);
return;
}
vis[x][y] = true; //防止重复访问,环的情况
for(int k = 0;k < 4;k++) {
int newx = x + dir[k][0];
int newy = y + dir[k][1];
if(inside(newx,newy) && !vis[newx][newy] && broke[newx][newy] > time) {
dfs(newx,newy,time+1);
}
}
}
int main() {
int n;cin>>n;
int t,x,y;
fill(broke[0],broke[0]+310*310,1e9); //默认都可达
broke[0][0] = 1;
for(int i = 1;i <= n;i++) {
cin>>t>>x>>y;
broke[x][y] = min(broke[x][y],t); //点燃中间(需要存储时间最小的)
if(inside(x+1,y)) { //点燃四周
broke[x+1][y] = min(broke[x+1][y],t);
}
if(inside(x-1,y)) {
broke[x-1][y] = min(broke[x-1][y],t);
}
if(inside(x,y-1)) {
broke[x][y-1] = min(broke[x][y-1],t);
}
if(inside(x,y+1)) {
broke[x][y+1] = min(broke[x][y+1],t);
}
}
dfs(0,0,0);
cout<<ans;
return 0;
}
by metaphysis @ 2020-04-22 12:36:48
@小豆子范德萨
您能用您自己的话描述一下解题逻辑吗?这样做,既方便别人判断您的解题思路是否正确,也有利于您自己理清解题思路,以便于后续检查代码实现是否存在问题。
by 小豆子范德萨 @ 2020-04-22 13:34:42
就像我代码中写到的。 读入这块:
搜索这块: 从(0,0)开始dfs搜索、判断周围的 是否没有被烧焦(这里用时间来判断)
by metaphysis @ 2020-04-22 16:00:55
@小豆子范德萨
(1)题目翻译有问题,流星的数据格式是
(2)您在初始化时将原点的撞击时间设置为1,不知为何原因?
您先处理上述两个问题,然后再看看。
by metaphysis @ 2020-04-22 16:06:39
输出时,当无解时,需要输出-1。
by 小豆子范德萨 @ 2020-04-22 20:57:03
@metaphysis 谢谢点播