原题链接：http://codeforces.com/gym/100203/attachments/download/1702/statements.pdf
题解
首先寻找每个I，然后枚举形状，如果匹配的话，就将源点连一条边到当前匹配的W，再从W连条边到I，I需要拆点，然后将拆点后面的那个点连接到N，从N连接到汇点。所有边的容量都是1。需要注意避免产生重边。然后最大流就是答案。
代码
#include#include #include #include #include #include #include #define MAX_V 1500#define MAX_N 10004#define INF 2500005using namespace std;struct edge{ int to,cap,rev;bool isRev;};vector G[MAX_N];int level[MAX_V];int iter[MAX_V];void add_edge(int from,int to,int cap) { G[from].push_back((edge) {to, cap, G[to].size(),0}); G[to].push_back((edge) { from, 0, G[from].size() - 1,1});}void bfs(int s) { memset(level, -1, sizeof(level)); queue que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } }}int dfs(int v,int t,int 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;}int max_flow(int s,int t) { int flow = 0; for (; ;) { bfs(s); if (level[t] < 0)return flow; memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } }}string ss[30];int n,m;//int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};int Hash(int x,int y) { return x * m + y;}int S=1234;int T=1313;bool vis[MAX_V];void AddEdges(int W,int I,int N) { if (!vis[W]) add_edge(S, W, 1); add_edge(W, I, 1); add_edge(I + n * m + 5, N, 1); if (!vis[N]) add_edge(N, T, 1); vis[W] = vis[N] = 1;}int main() { cin.sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < n; i++) cin >> ss[i]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (ss[i][j] != 'I')continue; add_edge(Hash(i, j), Hash(i, j) + n * m+5, 1); int u, v; u = j - 1; v = j + 1; if (u >= 0 && v < m) { if (ss[i][u] == 'N' && ss[i][v] == 'W')swap(u, v); if (ss[i][u] == 'W' && ss[i][v] == 'N') AddEdges(Hash(i, u), Hash(i, j), Hash(i, v)); } u = i - 1; v = i + 1; if (u >= 0 && v < n) { if (ss[u][j] == 'N' && ss[v][j] == 'W')swap(u, v); if (ss[u][j] == 'W' && ss[v][j] == 'N') AddEdges(Hash(u, j), Hash(i, j), Hash(v, j)); } u = j - 1; v = i - 1; if (u >= 0 && v >= 0) { if (ss[i][u] == 'N' && ss[v][j] == 'W') AddEdges(Hash(v, j), Hash(i, j), Hash(i, u)); if (ss[i][u] == 'W' && ss[v][j] == 'N') AddEdges(Hash(i, u), Hash(i, j), Hash(v, j)); } u = i - 1; v = j + 1; if (u >= 0 && v < m) { if (ss[u][j] == 'N' && ss[i][v] == 'W') AddEdges(Hash(i, v), Hash(i, j), Hash(u, j)); if (ss[u][j] == 'W' && ss[i][v] == 'N') AddEdges(Hash(u, j), Hash(i, j), Hash(i, v)); } u = j + 1; v = i + 1; if (u < m && v < n) { if (ss[i][u] == 'N' && ss[v][j] == 'W') AddEdges(Hash(v, j), Hash(i, j), Hash(i, u)); if (ss[i][u] == 'W' && ss[v][j] == 'N') AddEdges(Hash(i, u), Hash(i, j), Hash(v, j)); } u = i + 1; v = j - 1; if (u < n && v >= 0) { if (ss[u][j] == 'N' && ss[i][v] == 'W') AddEdges(Hash(i, v), Hash(i, j), Hash(u, j)); if (ss[u][j] == 'W' && ss[i][v] == 'N') AddEdges(Hash(u, j), Hash(i, j), Hash(i, v)); } } int f = max_flow(S, T); cout << f << endl; return 0;}