PKU 2920 Mine Map
http://poj.org/problem?id=2920
地雷が埋め込まれているマップを中央から地雷を避けて探索しろというような問題。
読解してBFS
訪れたところをチェックし忘れてMLEしました。
int dx[]={0,1,0,-1,1,1,-1,-1,0},dy[]={1,0,-1,0,1,-1,1,-1,0}; bool mine[300][300]; char out[400][400]; void solve(){ int n,m; cin>>n>>m; memset(mine,0,sizeof(mine)); memset(out,0,sizeof(out)); rep(i,m){ int x,y; cin>>x>>y; --x,--y; out[x][y]='*'; rep(j,9){ int nx=x+dx[j],ny=y+dy[j]; if(0>min(nx,ny) || n<=max(nx,ny))continue; mine[nx][ny]=true; } } queue<PI> q; q.push(mp(n/2,n/2)); while(!q.empty()){ int cx=q.front().F; int cy=q.front().S; q.pop(); if(out[cx][cy])continue; if(mine[cx][cy]){ out[cx][cy]='#'; continue; } out[cx][cy]='.'; rep(i,8){ int nx=cx+dx[i],ny=cy+dy[i]; if(min(nx,ny)<0 || max(nx,ny)>=n || out[nx][ny])continue; q.push(mp(nx,ny)); } } rep(i,n){ rep(j,n){ if(out[i][j])cout<<out[i][j]; else cout<<'?'; } cout<<endl; } cout<<endl; } main(){ int T; cin>>T; rep(sc,T){ printf("Scenario #%d:\n",sc+1); solve(); } }