Submission #10817226
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long int ll;
struct Edge{
int to,rev; ll cap;
Edge(int to,ll cap,int rev):to(to),cap(cap),rev(rev){}
};
// ここの値に注意!!
const int N=20500;
const ll INF=1e9;
vector<Edge> g[N];
int level[N];
int iter[N];
void add_edge(int s,int t,ll c){
g[s].push_back(Edge(t,c,g[t].size()));
g[t].push_back(Edge(s,0,g[s].size()-1));
}
void bfs(int s){
memset(level,-1,sizeof(level));
queue<int> q;
level[s]=0;
q.push(s);
while(q.size()){
int v=q.front(); q.pop();
for(auto &e:g[v]){
if(e.cap>0&&level[e.to]<0){
level[e.to]=level[v]+1;
q.push(e.to);
}
}
}
}
ll dfs(int v,int t,ll f){
if(v==t)return f;
for(int &i=iter[v];i<g[v].size();i++){
Edge &e=g[v][i];
if(e.cap>0&&level[v]<level[e.to]){
int d=dfs(e.to,t,min(f,e.cap));
if(d>0){
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
ll max_flow(int s,int t){
ll flow=0;
while(1){
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0){
flow+=f;
}
}
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char fi[110][110];
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int h,w; cin >> h >> w;
int s=h*w*2,t=h*w*2+1;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin >> fi[i][j];
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
int p=i*w+j; int q=p+h*w;
if(fi[i][j]=='X'){
if(i==0||i==h-1||j==0||j==w-1){
cout << -1 << endl;
return 0;
}
add_edge(s,p,INF);
add_edge(p,q,INF);
}else{
add_edge(p,q,1);
}
if(i==0||i==h-1||j==0||j==w-1){
add_edge(q,t,INF);
}
for(int k=0;k<4;k++){
int nx=dx[k]+i,ny=dy[k]+j;
if(0<=nx&&nx<h&&0<=ny&&ny<w){
add_edge(q,nx*w+ny,INF);
}
}
}
}
cout << max_flow(s,t) << endl;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
KKT89 |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
2013 Byte |
Status |
AC |
Exec Time |
41 ms |
Memory |
3584 KB |
Judge Result
Set Name |
All |
Score / Max Score |
150 / 150 |
Status |
|
Set Name |
Test Cases |
All |
00_sample.txt, 01_sample.txt, 02_sample.txt, 10_rand_00.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 11_hashi_00.txt, 11_hashi_01.txt, 11_hashi_02.txt, 12_rect_00.txt, 12_rect_01.txt, 12_rect_02.txt, 99_all_one.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample.txt |
AC |
2 ms |
896 KB |
01_sample.txt |
AC |
1 ms |
768 KB |
02_sample.txt |
AC |
2 ms |
896 KB |
10_rand_00.txt |
AC |
2 ms |
896 KB |
10_rand_01.txt |
AC |
2 ms |
1024 KB |
10_rand_02.txt |
AC |
11 ms |
1792 KB |
10_rand_03.txt |
AC |
12 ms |
1792 KB |
10_rand_04.txt |
AC |
8 ms |
3584 KB |
10_rand_05.txt |
AC |
13 ms |
3584 KB |
10_rand_06.txt |
AC |
7 ms |
1792 KB |
10_rand_07.txt |
AC |
13 ms |
2560 KB |
10_rand_08.txt |
AC |
25 ms |
3328 KB |
11_hashi_00.txt |
AC |
1 ms |
768 KB |
11_hashi_01.txt |
AC |
2 ms |
1280 KB |
11_hashi_02.txt |
AC |
2 ms |
768 KB |
12_rect_00.txt |
AC |
41 ms |
3200 KB |
12_rect_01.txt |
AC |
7 ms |
1536 KB |
12_rect_02.txt |
AC |
8 ms |
2944 KB |
99_all_one.txt |
AC |
2 ms |
768 KB |