生活随笔
收集整理的這篇文章主要介紹了
Fire!——两个BFS
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
【題目描述】
【題目分析】
看到題目后很清楚是兩個BFS，可是我覺得對于火的BFS可以轉換成判斷，我的做法是將火的位置全部記錄下來，然后判斷某個位置距離每個火的步數是否小于當前步數，可是錯了，還不清楚為什么（有可能是因為沒有記憶化復雜度太高？但是為什么是wa不是超時），改成BFS后就過了
【AC代碼】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<climits>
#include<set>using namespace std
;const int MAXN
=1005;
int n
,m
,sx
,sy
,ans
;
char map
[MAXN
][MAXN
];
int vis
[MAXN
][MAXN
];
struct node
{int x
,y
,step
;
}t
,p
,S
;
int Time
[MAXN
][MAXN
];
const int drc
[4][2]={1,0,-1,0,0,1,0,-1};
queue
<node
> fire
;void init()
{int u
,v
;while(!fire
.empty()){p
=fire
.front(); fire
.pop();for(int i
=0;i
<4;i
++){u
=p
.x
+drc
[i
][0]; v
=p
.y
+drc
[i
][1];if(u
<0 || u
>n
-1 || v
<0 || v
>m
-1) continue;if(map
[u
][v
]=='#') continue;if(p
.step
+1>=Time
[u
][v
]) continue;Time
[u
][v
]=p
.step
+1;t
.x
=u
; t
.y
=v
; t
.step
=p
.step
+1;fire
.push(t
);}}
}bool BFS()
{int u
,v
;memset(vis
,0,sizeof(vis
));queue
<node
> q
;q
.push(S
); vis
[S
.x
][S
.y
]=1;while(!q
.empty()){p
=q
.front(); q
.pop();if(p
.x
==0 || p
.x
==n
-1 || p
.y
==0 || p
.y
==m
-1){ans
=p
.step
+1;return true;}for(int i
=0;i
<4;i
++){u
=p
.x
+drc
[i
][0]; v
=p
.y
+drc
[i
][1];if(u
<0 || u
>n
-1 || v
<0 || v
>m
-1) continue;if(map
[u
][v
]=='#' || vis
[u
][v
]) continue;if(p
.step
+1>=Time
[u
][v
]) continue;vis
[u
][v
]=1;t
.x
=u
; t
.y
=v
; t
.step
=p
.step
+1;q
.push(t
);}}return false;
}int main()
{int T
;scanf("%d",&T
);while(T
--){while(!fire
.empty()) fire
.pop();memset(map
,0,sizeof(map
));scanf("%d%d",&n
,&m
);ans
=0;memset(Time
,0x3f,sizeof(Time
));for(int i
=0;i
<n
;i
++){scanf("%s",map
[i
]);for(int j
=0;j
<m
;j
++){if(map
[i
][j
]=='J'){S
.x
=i
; S
.y
=j
; S
.step
=0;map
[i
][j
]='.';}else if(map
[i
][j
]=='F'){t
.x
=i
; t
.y
=j
; t
.step
=0;Time
[i
][j
]=0;fire
.push(t
);}}}init();if(BFS()){printf("%d\n",ans
);}else{printf("IMPOSSIBLE\n");}}return 0;
}
剛才記憶化了一下試了一下還是不行，并不知道為什么
【wa代碼】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<climits>
#include<set>using namespace std
;const int MAXN
=1005;
int n
,m
,sx
,sy
,ans
;
char map
[MAXN
][MAXN
];
int vis
[MAXN
][MAXN
];
struct node
{int x
,y
,step
;
}t
,p
,S
;
struct node1
{int x
,y
;}fire
[MAXN
*MAXN
];
int Time
[MAXN
][MAXN
];
int cnt
;
const int drc
[4][2]={1,0,-1,0,0,1,0,-1};
void init()
{int u
,v
;for(int i
=0;i
<n
;i
++){for(int j
=0;j
<m
;j
++){if(map
[i
][j
]=='#') continue;for(int k
=0;k
<cnt
;k
++){Time
[i
][j
]=min(Time
[i
][j
],abs(i
-fire
[k
].x
)+abs(j
-fire
[k
].y
));}}}
}bool BFS()
{int u
,v
;memset(vis
,0,sizeof(vis
));queue
<node
> q
;q
.push(S
); vis
[S
.x
][S
.y
]=1;while(!q
.empty()){p
=q
.front(); q
.pop();if(p
.x
==0 || p
.x
==n
-1 || p
.y
==0 || p
.y
==m
-1){ans
=p
.step
+1;return true;}for(int i
=0;i
<4;i
++){u
=p
.x
+drc
[i
][0]; v
=p
.y
+drc
[i
][1];if(u
<0 || u
>n
-1 || v
<0 || v
>m
-1) continue;if(map
[u
][v
]=='#' || vis
[u
][v
]) continue;if(p
.step
+1>=Time
[u
][v
]) continue;vis
[u
][v
]=1;t
.x
=u
; t
.y
=v
; t
.step
=p
.step
+1;q
.push(t
);}}return false;
}void show()
{for(int i
=0;i
<cnt
;i
++){printf("%d %d\n",fire
[i
].x
,fire
[i
].y
);}for(int i
=0;i
<n
;i
++){for(int j
=0;j
<m
;j
++){printf("%d ",Time
[i
][j
]);}printf("\n");}
}int main()
{int T
;scanf("%d",&T
);while(T
--){memset(map
,0,sizeof(map
));scanf("%d%d",&n
,&m
);cnt
=0; ans
=0;memset(fire
,0,sizeof(fire
));memset(Time
,0x3f,sizeof(Time
));for(int i
=0;i
<n
;i
++){scanf("%s",map
[i
]);for(int j
=0;j
<m
;j
++){if(map
[i
][j
]=='J'){S
.x
=i
; S
.y
=j
; S
.step
=0;map
[i
][j
]='.';}else if(map
[i
][j
]=='F'){fire
[cnt
].x
=i
; fire
[cnt
].y
=j
;cnt
++;}}}init();if(BFS()){printf("%d\n",ans
);}else{printf("IMPOSSIBLE\n");}}return 0;
}
總結
以上是生活随笔為你收集整理的Fire!——两个BFS的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
