2019-05-14 21:49:16 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; bool flag; queue<int> que; const int INF = 1e9+7; string s[501]; int d[501][501]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,1,-1}; int R,C,K; void bfs(int x,int y,int cost){ for(int i=0;i<501;i++)for(int j=0;j<501;j++)d[i][j]=INF; que.push(1000*x+y); d[x][y]=0; flag = true; while(!que.empty()){ int temp = que.front(); que.pop(); int tx = temp/1000; int ty = temp%1000; if(d[tx][ty]==K-1)continue; for(int i=0;i<4;i++){ if(s[tx+dx[i]][ty+dy[i]]=='o'){ if(d[tx+dx[i]][ty+dy[i]]>d[tx][ty]+1)d[tx+dx[i]][ty+dy[i]]=d[tx][ty]+1; que.push((tx+dx[i])*1000+ty+dy[i]); }else{ flag = false; break; } } if(flag==false){ break; } } } bool check(int x,int y){ flag = false; bfs(x,y,0); while (!que.empty()) que.pop(); return flag; } int main(void){ cin >> R >> C >> K; for(int i=0;i<R;i++){ cin >> s[i]; } int ans = 0; for(int i=K-1;i<=R-K;i++){ for(int j=K-1;j<=C-K;j++){ if(s[i][j]=='o'){ if(check(i,j))ans++; } } } cout << ans << endl; }
RECOMMEND