首页 > 代码库 > hdu 5546
hdu 5546
dfs暴力,比赛的时候没仔细想,后来自己想想思路并不是很清晰,写了不对,后来看了大佬的代码,发现还是有很多细节需要注意的,特别是联通块的标记,现在理解更加透彻了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t,ans,cnt,zz; int mapp[15][15]; int vis[15][15]; pair<int,int> a[100]; int ss[5][3]={{1,0},{0,1},{-1,0},{0,-1}}; void dfs(int x,int y) { vis[x][y]=zz;//标记自己的联通块,但并不与其他连通块冲突 for(int i=0;i<4;i++) { int dx=x+ss[i][0],dy=y+ss[i][1]; if(dx<0||dx>=9||dy<0||dy>=9||vis[dx][dy]==zz||mapp[dx][dy]==-1) continue; else if(!mapp[dx][dy]) { cnt++;//如果有".",就cnt++ vis[dx][dy]=zz;//“.”也要标记,防止找到同一个"." } else dfs(dx,dy);//只有"o",才进行dfs } } int main() { while(~scanf("%d",&t)) { for(int hh=1; hh<=t; hh++) { ans=0; memset(vis,0,sizeof(vis)); memset(mapp,0,sizeof(mapp)); for(int i=0; i<9; i++) for(int j=0; j<9; j++) { char tt; cin >> tt; if(tt==‘o‘) mapp[i][j]=1; else if(tt==‘x‘) mapp[i][j]=-1; if(mapp[i][j]==1) a[ans++]=make_pair(i,j); } zz=0; int flag=0; for(int i=0;i<ans;i++) { if(!vis[a[i].first][a[i].second]) { zz++; cnt=0; dfs(a[i].first,a[i].second); if(cnt==1)//最关键的标记,也就是有几个"." { flag=1; break; } } } if(flag) printf("Case #%d: Can kill in one move!!!\n",hh); else printf("Case #%d: Can not kill in one move!!!\n",hh); } } return 0; }
hdu 5546
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。