POJ 1856 Sea Battle G++dfs 背

xiaoxiao2021-02-28  89

#include <iostream> #include <cstdio> using namespace std; //英语 抄博友程序 dfs 背 char da[1008][1008]; int dx[4]={0, 0,1,-1}; int dy[4]={1,-1,0, 0}; int n,m; void dfs(int x,int y) { da[x][y]='.'; for(int i=0;i<4;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx>=0 && tx<n && ty>=0 && ty<m) { if(da[tx][ty]=='#') { dfs(tx,ty); } } } } bool bad()//抄博友程序 { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(j+1<m && i+1<n) if(da[i][j]=='.'&& da[i][j+1]=='#' && da[i+1][j]=='#') { return true; } if(j-1>=0&& i-1>=0) if(da[i][j]=='.' && da[i][j-1]=='#' && da[i-1][j]=='#') { return true; } if(j-1>=0 && i+1<n) if(da[i][j]=='.' && da[i][j-1]=='#' && da[i+1][j]=='#') { return true; } if(j+1<m && i-1>=0) if(da[i][j]=='.' && da[i][j+1]=='#' && da[i-1][j]=='#') { return true; } } } return false; } int main() { while(1) { //cin>>n>>m; scanf("%d %d",&n,&m); //cout<<n<<" "<<m<<endl; if(n==0 && m==0) { break; } for(int i=0;i<n;i++) { scanf("%s",da[i]);//抄博友程序 } /* for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cout<<da[i][j]; //scanf("%c",&da[i][j]); } cout<<endl; }*/ if(bad()) { cout<<"Bad placement."<<endl; }else { int js=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(da[i][j]=='#') { js++; dfs(i,j); } } } cout<<"There are "<<js<<" ships."<<endl; } } return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-24931.html

最新回复(0)