Submission #1439746

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int V, E, src, snk;
vector<int> la, nxt, oppo, capa;
void init() {
    E = 0;
    la.clear(); nxt.clear(); oppo.clear(); capa.clear();
    la = vector<int>(V, -1);
}
void add(int u, int v, int c) {
    nxt.push_back(la[u]);
    la[u] = E++;
    oppo.push_back(v);
    capa.push_back(c);
}
vector<int> dist;
queue<int> q;
bool bfs() {
    dist = vector<int>(V, -1);
    q.push(src);
    dist[src] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(capa[i] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist[snk] != -1;
}
vector<int> laa;
int dfs(int u, int f) {
    if(u == snk) return f;

    for(int i = laa[u]; i != -1; i = nxt[i]) {
        laa[u] = i;
        int v = oppo[i];
        if(capa[i] && dist[v] == dist[u] + 1) {
            if(int tmp = dfs(v, min(capa[i], f))) {
                capa[i] -= tmp;
                capa[i ^ 1] += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int dinic() {
    int tf = 0;
    while(bfs()) {
        laa = la;
        while(int tmp = dfs(src, 1e8)) tf += tmp;
    }
    return tf;
}

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int H, W;
vector<string> G;

int main() {
    scanf("%d %d", &H, &W);

    G.resize(H);

    for(int i = 0; i < H; i++) {
        cin>>G[i];
    }

    V = 2*H*W + 2, src = V - 2, snk = V - 1;
    init();

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            add(i*W + j, H*W + i*W + j, (G[i][j] == '.'? 1 : 1e8));
            add(H*W + i*W + j, i*W + j, 0);

            if(G[i][j] == 'X') {
                add(src, i*W + j, 1e8);
                add(i*W + j, src, 0);
            }

            bool edge = false;
            for(int k = 0; k < 4; k++) {
                int ni = i + dy[k];
                int nj = j + dx[k];
                if(ni < 0 || H <= ni || nj < 0 || W <= nj) {
                    edge = true;
                    continue;
                }
                add(H*W + i*W + j, ni*W + nj, 1e8);
                add(ni*W + nj, H*W + i*W + j, 0);
            }

            if(edge) {
                add(H*W + i*W + j, snk, 1e8);
                add(snk, H*W + i*W + j, 0);
            }

            if(edge && G[i][j] == 'X') {
                printf("-1\n");
                return 0;
            }
        }
    }

    printf("%d\n", dinic());
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &H, &W);
                           ^

Judge Result