このくらい簡単な問題が出てくれたらレートあがるんだけどなあ……
#include<stdio.h> #include<algorithm> #include<vector> #include<string> #include<queue> using namespace std; const int D_MAX_V=10000; const int D_v_size=10000; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } class FoxAndGo3{ public: int maxEmptyCells(vector<string> board){ int n=board.size(); int val=0; int S=n*n*2+1; int T=n*n*2+2; int INF=99999999; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='o'){ val++; add_edge(i*n+j,T,1); if(i&&board[i-1][j]=='.'){ add_edge((i-1)*n+j,i*n+j,INF); } if(j&&board[i][j-1]=='.'){ add_edge(i*n+j-1,i*n+j,INF); } if(i<n-1&&board[i+1][j]=='.'){ add_edge((i+1)*n+j,i*n+j,INF); } if(j<n-1&&board[i][j+1]=='.'){ add_edge(i*n+j+1,i*n+j,INF); } } if(board[i][j]=='.'){ val++; add_edge(S,i*n+j,1); add_edge(n*n+i*n+j,T,0); add_edge(i*n+j,n*n+i*n+j,INF); } } } return val-max_flow(S,T); } };