1 solutions
-
0
C++ :
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <string> #include <vector> using namespace std; #define SZ(v) int((v).size()) #define FR(i,a,b) for(int i=(a);i<(b);++i) #define FOR(i,n) FR(i,0,n) #define FORI(i,v) FOR(i,SZ(v)) #define CLR(x,a) memset(x,a,sizeof(x)) #define setmax(a,b) a = max(a,b) #define setmin(a,b) a = min(a,b) typedef long long ll; int R,C; char buf[16]; int deg[16][16]; int nod[16][16][4]; const int MAXV = 514; bool mark[MAXV]; int cap[MAXV][MAXV]; vector<int> edg[MAXV]; const int s=MAXV-2,t=MAXV-1; void connect(int v, int w, int u) { cap[v][w] = u; cap[w][v] = 0; edg[v].push_back(w); edg[w].push_back(v); } int dr[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 }; const int inf = 123456789; int dfs(int v, int flocap=inf) { if (v==t) return flocap; if (mark[v]) return 0; mark[v] = 1; FORI(i,edg[v]) { int w = edg[v][i]; if (cap[v][w]) { int f = dfs(w, min(flocap, cap[v][w])); if (f) { cap[v][w] -= f; cap[w][v] += f; return f; } } } return 0; } void doit() { scanf("%d%d",&R,&C); if (R==0) exit(0); FOR(v,MAXV) edg[v].clear(); CLR(cap,0); FOR(r,R) { FOR(c,C) { scanf(" %s",buf); if (0==strcmp("x",buf)) deg[r][c]=0; else deg[r][c] = strlen(buf); } } int next = 0; FOR(r,R) FOR(c,C) { if (deg[r][c] != 2) { FOR(k,4) nod[r][c][k] = next; if ((r+c)%2) connect(s, next, deg[r][c]); else connect(next, t, deg[r][c]); ++next; } else { FOR(k,4) nod[r][c][k] = next + (k%2); if ((r+c)%2) FOR(k,2) connect(s, next+k, 1); else FOR(k,2) connect(next+k, t, 1); next += 2; } } FOR(r,R) FOR(c,C) if ((r+c)%2) { FOR(k,4) { int r2 = r+dr[k], c2 = c+dc[k]; if (r2<0||r2>=R||c2<0||c2>=C) continue; int k2 = (k+2)%4; connect(nod[r][c][k], nod[r2][c2][k2], 1); } } while (1) { CLR(mark,0); int f = dfs(s); if (f == 0) break; } int ed=0,od=0; FOR(r,R) FOR(c,C) { if ((r+c)%2) od += deg[r][c]; else ed += deg[r][c]; } bool happy = 1; FOR(v,MAXV) if (cap[s][v] || cap[v][t]) happy = 0; printf("%s\n", happy ? "SOLVABLE" : "UNSOLVABLE"); } int main() { while (1) doit(); }
- 1
Information
- ID
- 18757
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By