[BFS] POJ 2251 Dungeon Master | POJ 3278 Catch That Cow | POJ 3126 Prime Path | POJ 3414 Po
BFS（1）
BFS（2）：queue中状态结构体类型不止不止当前val
BFS（3）：多源BFS
BFS(1)
2251
#include"stdio.h"
#include"limits.h"
#include"string.h"
#include
using namespace std;
const int MAX_L = 32;
const int MAX_R = 32;
const int MAX_C = 32;
struct Pos{
int i;int j;int k;
int lv;
Pos(int i_,int j_,int k_,int lv_):i(i_),j(j_),k(k_),lv(lv_){}
};
char dungeon[MAX_L][MAX_R][MAX_C];
char vist[MAX_L][MAX_R][MAX_C];
int L,R,C;
int S[3];
int E[3];
int min_n=INT_MAX;
int n=0;
int to[3][6]={{-1,+1,0,0,0,0},
{0,0,-1,+1,0,0},
{0,0,0,0,-1,+1}};
bool isValid(int i,int j,int k){
if(i<0||i>=L || j<0||j>=R || k<0||k>=C) return false;
if(dungeon[i][j][k]=='#') return false;
if(vist[i][j][k]) return false;
return true;
}
int bfs(int si,int sj,int sk){
queue Q;
Q.push(Pos(si,sj,sk,0));
vist[si][sj][sk]=true;
while(!Q.empty()){
Pos p=Q.front();
int i=p.i; int j=p.j; int k=p.k; int lv=p.lv;
Q.pop();
if(dungeon[i][j][k]=='E') {
return lv;
}
for(int t=0;t<6;t++){
// 判断条件放在push前，相比于取出可能无效数据后判断，减少push/pop
if(isValid(i+to[0][t],j+to[1][t],k+to[2][t])){
// 访问标记与push两个操作同时进行。相比于pop后再标记可以实现更有效的剪枝
vist[i+to[0][t]][j+to[1][t]][k+to[2][t]]=true;
Q.push(Pos(i+to[0][t],j+to[1][t],k+to[2][t],lv+1));
}
}
}
return -1;
}
int main(){
while(1){
scanf("%d %d %d",&L,&R,&C);
if(!L &&!R && !C) break;
memset(dungeon,'#',MAX_L*MAX_R*MAX_C);
memset(vist,0,MAX_L*MAX_R*MAX_C);
min_n=INT_MAX;
n=0;
for(int i=0;i 3278
#include"stdio.h"
#include"string.h"
#include
using namespace std;
const int MAX_N=100010;
int N,K;
int vist[MAX_N];
bool check(int x){
if(x<0 || x>100000) return false;
if(vist[x]) return false;
return true;
}
int bfs(){
queue Q;
Q.push(N);
vist[N]=1;
while(!Q.empty()){
int x = Q.front();
Q.pop();
if(x==K) return vist[x]-1;
int choice[3]={x+1,x-1,2*x};
for(int i=0;i<3;i++){
if(check(choice[i])){
vist[choice[i]] = vist[x]+1;
Q.push(choice[i]);
}
}
}
}
int main(){
memset(vist,0,MAX_N);
scanf("%d %d",&N,&K);
int x = bfs();
printf("%d\n",x);
}
BFS(2)
3126
#include"stdio.h"
#include"string.h"
#include
#include
using namespace std;
int isPrime[10000];// queue中元素类型用结构体维护除了val，step，还有vis
struct St{
int x; // 4-digit 0~9
int pre_vis;// 0~3
int step;
St(){}
St(int x_,int p_,int s_):x(x_),pre_vis(p_),step(s_){}
};
int pow[]={1,10,100,1000};
int main(){
memset(isPrime,1,sizeof(isPrime));
isPrime[1]=false;
for(int i=2;i<10000;i++){
if(!isPrime[i]) continue;
for(int k=i+i;k<10000;k+=i){
isPrime[k] = 0;
}
}
int N;
scanf("%d",&N);
for(int n=0;n S; // 若不加这个set防止path成环，会TLE
queue Q;
Q.push(St(src,-1,0));
St st;
while(!Q.empty()){
st = Q.front();
Q.pop();
if(st.x==dst) break;
for(int i=0;i<4;i++){
if(i==st.pre_vis) continue;
for(int j=0;j<10;j++){
if(i==3 && j==0) continue; // without leading zero
// change digit i
int dig = (st.x%(int)pow[i+1]) / pow[i];
if(j==dig) continue;
int nextx = st.x - (dig-j)*pow[i];
if(isPrime[nextx] && S.count(nextx)==0) {
Q.push(St(nextx, i, st.step+1));
S.insert(nextx);
}
}
}
}
printf("%d\n",st.step);
}
}
3414
#include
#include"math.h"
#include
#include
#include
// codeblocks上可以不#include，poj上必须include
#include
using namespace std;
typedef pair Pair;
// poj [Compile Error] non-aggregates cannot be initialized with initializer list
// vector otpt={"FILL","DROP","POUR"};
char otpt[3][5]={"FILL","DROP","POUR"};
struct Op{
int o;// 0-FILL,1-DROP,2-POUR
int p;// 1-pot1,2-pot2
Op(int o_,int p_):o(o_),p(p_){}
};
struct St{
int pot1,pot2;
vector path;
St(){}
St(int p1,int p2):pot1(p1),pot2(p2){}
St(int p1,int p2,vector p_):pot1(p1),pot2(p2),path(p_){}
};
int main(){
int A,B,C;
cin>>A>>B>>C;
/* 本来想用St做M集合中的元素类型 */
/* BFS(3)
FZU 2150 Fire Game 双起点BFS
- 状态包含 {n, m} or {n1, m1, n2, m2}？前者。若用后者，DFS会TLE，BFS会MLE
- 用DFS or BFS？双起点（有关联的两棵树）：无法用dfs，用bfs
#include
#include
#include
#include"string.h"
#include"math.h"
using namespace std;
struct St{
int n,m;
int s;
St(){}
St(int n_,int m_,int s_):n(n_),m(m_),s(s_){}
};
struct Pos{
int n,m;
Pos(int n_,int m_):n(n_),m(m_){}
};
const int MAX_N=10;
const int MAX_M=10;
char board[MAX_N][MAX_M];
int step[MAX_N][MAX_M];
int N,M;
const int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};// 为什么要维护所有#的位置？// 若用四重for循环，重复多；若内层两层for循环初始化为外层两层的值，ii=i, jj=j，实现的逻辑是（错误的：）接着遍历子矩阵，而非剩下所有。
vector grass;
void display(){
for(int i=0;i Q;
Q.push(St(n1,m1,0));
Q.push(St(n2,m2,0));
step[n1][m1] = 0;
step[n2][m2] = 0;
St p;
while(!Q.empty()){
p = Q.front();
Q.pop();
for(int i=0;i<4;i++){
int x=p.n+to[i][0];
int y=p.m+to[i][1];
if(x<0 || x>=N ||y<0 || y>=M) continue;
if(board[x][y]!='#') continue;
if(step[x][y]>=0) continue;
step[x][y] = p.s+1;
Q.push(St(x,y,p.s+1));
}
}
return p.s;
}/* 曾经的思路 */
/* 先dfs得到连通分量的个数，然后分类讨论：/* >2，返回-1；/* =2，两个区域分别单起点搜索；/* =1，单区域双起点搜索。/* 改进的思路 *//* 是否需要对连通分量个数分类讨论？简化：统一双起点BFS，搜索结束后check/* 因此不需要实现搜索一遍求连通分量个数。事实上，这么做TLE /* -------- */
int solve(){
int mins=0x3fffffff;
for(unsigned i=0;i UVA 11624 Fire
- 多个火和单个人公用一个队列还是分两个队列？
- 都可以，关键是每次火和人都只能加一层深度。
- 因此while不应以队列empty为判断条件，而应以该层火或人的数量作为while循环次数。
- 火和人的vis数组应当共享（作全局变量）还是私有（增加path作为状态struct的数据成员）？
- 火的vis数组显然做全局变量：已经燃烧到的地方终止进一步搜索
- 人的vis数组：一条搜索路径visit过的地方，另一条搜索路径还需要再搜么？错过，仔细想想（不需要，否则TLE
- 人无路可走的条件是什么？
- 当前深度层所有搜索路径的所有方向都无路可走
- 错过：当前深度层有一条搜索路径的所有方向无路可走
#include"stdio.h"
#include"string.h"
#include
#include
#include
#include
using namespace std;
typedef pair Coord;
struct PosF{
int r,c;
PosF(){}
PosF(int r_,int c_):r(r_),c(c_){}
};
struct PosJ{
int r,c;
int s;//step
PosJ(){}
PosJ(int r_,int c_,int s_):r(r_),c(c_),s(s_){}
};
const int MAXRC=1003;
int R,C;
char maze[MAXRC][MAXRC];
int visF[MAXRC][MAXRC];// 0-not visited, 1-visited
int visJ[MAXRC][MAXRC];
std::vector Fs;//Fires
Coord Joe;
const int to[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
queue QF;
queue QJ;
void bfsF(){
int nF=QF.size();
while((nF--)){
PosF pF = QF.front();
QF.pop();
for(int i=0;i<4;i++){
int x = pF.r + to[i][0];
int y = pF.c + to[i][1];
if(x<0 ||x>=R ||y<0 ||y>=C) continue;
if(visF[x][y]) continue;
if(maze[x][y]=='#') continue;
QF.push(PosF(x,y));
visF[x][y]=1;
}
}
}
int bfsJ(){
int nJ=QJ.size();
bool alive=false;
while((nJ--)){
PosJ pJ = QJ.front();
QJ.pop();
if(pJ.r==0 || pJ.r==R-1 || pJ.c==0 || pJ.c==C-1) return pJ.s;
for(int i=0;i<4;i++){
int x = pJ.r + to[i][0];
int y = pJ.c + to[i][1];
if(x<0 ||x>=R ||y<0 ||y>=C) continue;
if(maze[x][y]=='#') continue;
if(visF[x][y]) continue;
if(visJ[x][y]) continue;
if(x==0 || x==R-1 || y==0 || y==C-1) return pJ.s+1;
alive=true;
visJ[x][y] = 1;
QJ.push(PosJ(x,y,pJ.s+1));
}
}
if(!alive) return -1;
else return 0;
}
int solve(){
for(int i=0;i S; S.insert(Coord(Joe.first,Joe.second));
QJ.push(PosJ(Joe.first,Joe.second,1));
visJ[Joe.first][Joe.second] = 1;
bfsF();
int ret;
while((ret = bfsJ())==0) bfsF();
return ret;
}
int main(){
int T;
scanf("%d",&T);
for(int t=0;t();
QF = queue();
scanf("%d %d",&R,&C);
for(int r=0;r