POJ 2920 Mine Map(BFS)
http://poj.org/problem?id=2920
题意:有一个n*n(n为奇数)的网格金库,金库中有地雷和空格,你从金库的正中间出发,首先如果你所在的当前格子的8个方向附近有地雷.那么你就不能走了,且标记你的当前格子为’#’.如果8方向没地雷,你就把这8方向的格子都走一遍,且标记着8个格子为’.’ . 按照这个规则走过所有你能走的格子上去,并标记好.注意:地雷格子一开始就标记好为’*’.
分析:初始化一个map[n][n]=”??????...???”.然后用BFS从中间开始走,按照题意的规则标记且走格入队列即可.
不过注意:此题是8反向都可以走.
注意:如果我们走到了一个格子上,这个格子就可能为’.’或者为’#’.
取决于这个格子周围是否有地雷,如果有地雷,那么这个格子就是’#’,如果枚地雷,这个格子就是’.’.
任何我们没走过的格子只能是’*’
或 ‘?’.
且如果一个格子已经是’.’或’#’了,我们就不能再走上去了.也就是说我们只能走到那些’?’的格子上,然后判断出’?’格子的属性,如果’?’格子变成了’#’,那么我们就不能向8个方向扩展,如果’?’格子变成了’.’我们就必须向8个方向扩展.
AC代码:(本代码还能更快,因为我每次判断当前格子8向是否有雷使用了一个循环判断的,其实可以在读入地雷的时候就将它附近的格子cnt[nr][nc]值++,只要map[i][j]==?且cnt[i][j]>0的格子,那么这个格子周围一定有地雷.)
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=300+5;
struct Node
{
int r,c;
Node(int r,int c):r(r),c(c){}
};
int dr[]={-1,1,0,0,-1,1,-1,1};//上下左右,左上,左下,右上,右下
int dc[]={0,0,-1,1,-1,-1,1,1};
char map[maxn][maxn];
int n,m;//n*n网格,m个地雷
bool mine(int r,int c) //如果r,c格周围有地雷,返回true
{
for(int d=0;d<8;d++)
{
int nr=r+dr[d], nc=c+dc[d];
if(nr>=1&&nr<=n&&nc>=1&&nc<=n&&map[nr][nc]=='*') return true; //错误,这里nr,nc没有做越界判断
}
return false;
}
void BFS(int mr,int mc)
{
queue<Node> Q; //错误,这里多了一句Q.push语句
if(mine(mr,mc)) map[mr][mc]='#';
else map[mr][mc]='.';
if(map[mr][mc]=='.') Q.push(Node(mr,mc));
while(!Q.empty())
{
Node node=Q.front();Q.pop();//取出来的格子表示已经走到的格子且是'.'的格子
int r=node.r,c=node.c;
for(int d=0;d<8;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=1&&nr<=n&&nc>=1&&nc<=n&&map[nr][nc]=='?')
{
if(mine(nr,nc)) map[nr][nc]='#'; //错误,写成了min(r,c)
else map[nr][nc]='.';
if(map[nr][nc]=='.') Q.push(Node(nr,nc));
}
}
}
}
int main()
{
int T;scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]='?';
while(m--)
{
int r,c;
scanf("%d%d",&r,&c);
map[r][c]='*';
}
BFS((n+1)/2,(n+1)/2); //错误,这里写成了(n+1)/2了
printf("Scenario #%d:\n",kase);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%c",map[i][j]);
printf("\n");
}
puts("");
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ 3131 双向BFS解立体八数码问题
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
SPOJ3 AC程序 BF SPOJ3 AC程序 BF SPOJ3 AC程序 BF
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类