寻宝图（BFS)--题解

使用广度优先搜索BFS)核心代码分为以下几个步骤取出一个格子搜索格子将新的格子加入队列从而保证了每个格子只处理一次#includestdio.h#includestdbool.h#includestring.h#defineMAX100010intmain()intN,M;scanf(%d %d,N,M);// 加上外围一圈水这样就几乎不用判断边界了N2;M2;charmap[N][M];// 初始化整个地图为 0水地形for(inti0;iN;i)for(intj0;jM;j)map[i][j]0;// 读取内部地图从第1行第1列开始getchar();// 吸收第一行末尾的换行符for(inti1;iN-1;i){for(intj1;jM-1;j){map[i][j]getchar();}getchar();}// 访问标记数组bool visited[N][M];memset(visited,0,sizeof(visited));// 方向数组上、下、左、右这样不用写一堆ifintdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};intisland0;// 岛屿总数intgoodisland0;// 有宝藏的岛屿数// 手动实现队列BFS用intqueue_x[N*M],queue_y[N*M];intfront,rear;// 遍历所有内部格子真正的陆地只可能出现在内部for(inti1;iN-1;i){for(intj1;jM-1;j){// 如果是陆地且未被访问则发现新岛屿if(map[i][j]!0!visited[i][j]){island;bool has_treasurefalse;// BFS初始化frontrear0;queue_x[rear]i;queue_y[rear]j;rear;visited[i][j]true;while(frontrear){intxqueue_x[front];intyqueue_y[front];front;// 检查当前格子是否有宝藏if(map[x][y]2map[x][y]9){has_treasuretrue;}// 探索四个方向for(intk0;k4;k){intnxxdx[k];intnyydy[k];// 由于加了边界nx, ny一定在0~N-1,0~M-1内if(!visited[nx][ny]map[nx][ny]!0){visited[nx][ny]true;queue_x[rear]nx;queue_y[rear]ny;rear;}}}if(has_treasure){goodisland;}}}}printf(%d %d\n,island,goodisland);return0;}