【POJ】3133 Manhattan Wiring-白红宇

【POJ】3133 Manhattan Wiring

阅读量：6593 次

发布时间：2019-06-24

本文共 2800 字，大约阅读时间需要 9 分钟。

题意：n×m的网格，有2个2，2个3，他们不会重合。还有障碍1。现在求2到2的路径和3到3的路径互不相交的最短长度-2。（2<=n,m<=9）

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct H {	static const int M=1000007;	struct E { int next, to; }e[M<<1];	int mn[M], hash[M], cnt, ihead;	H() { cnt=ihead=0; memset(mn, 0x3f, sizeof mn); memset(hash, -1, sizeof hash); }	bool find(int x, int &pos) {		pos=x%M;		while(1) { if(hash[pos]==x) return 0; if(hash[pos]==-1) break; ++pos; if(pos==M) pos=0; }		hash[pos]=x;		return 1;	}	void ins(int a, int b) {		int pos; if(!find(a, pos)) { mn[pos]=min(mn[pos], b); return; }		mn[pos]=b; e[++cnt].next=ihead; ihead=cnt; e[cnt].to=pos;	}	void clr() { for(int i=ihead; i; i=e[i].next) hash[e[i].to]=-1, mn[e[i].to]=0x3f3f3f3f; ihead=cnt=0; }}T[2];int n, m, mp[12][12], all;#define BIT(a,b) ((a)<<((b)<<1))#define CLR(a,b) (a^=(a&BIT(3,b)))#define GET(a,b) (3&((a)>>((b)<<1)))bool next(int s, int row, int col, bool U, bool D, bool L, bool R, int id, int &t) {	if((!row&&U) || (!col&&L) || (row==n-1&&D) || (col==m-1&&R)) return 0;	if((D&&mp[row+1][col]==1) || (R&&mp[row][col+1]==1)) return 0;	int l=GET(s, col), u=GET(s, col+1), d=0, r=0;	if((L&&!l) || (!L&&l) || (U&&!u) || (!U&&u)) return 0;	if((l&&l!=id) || (u&&u!=id)) return 0;	t=s;	if(!l && !u) { if(D) d=id; if(R) r=id; }	else if(l && u) { if(l!=u || mp[row][col]>=1) return 0; }	else if(l && !u) { if(D) d=l; if(R) r=l; }	else if(!l && u) { if(D) d=u; if(R) r=u; }	CLR(t, col); CLR(t, col+1);	t|=BIT(d, col); t|=BIT(r, col+1);	if(col==m-1) t<<=2; t&=all;	return 1;}int bfs() {	int now=0, last=1;	T[now].clr();	T[now].ins(0, 0);	for(int row=0; row
        
         =1) {				if(next(s, row, col, 1, 0, 0, 0, id, t)) T[last].ins(t, d);				if(next(s, row, col, 0, 1, 0, 0, id, t)) T[last].ins(t, d);				if(next(s, row, col, 0, 0, 1, 0, id, t)) T[last].ins(t, d);				if(next(s, row, col, 0, 0, 0, 1, id, t)) T[last].ins(t, d);			}			else {				if(next(s, row, col, 0, 0, 0, 0, 0, t)) T[last].ins(t, d-1);				if(id==-1) {					for(int k=1; k<=2; ++k) {						if(next(s, row, col, 1, 1, 0, 0, k, t)) T[last].ins(t, d);						if(next(s, row, col, 1, 0, 1, 0, k, t)) T[last].ins(t, d);						if(next(s, row, col, 1, 0, 0, 1, k, t)) T[last].ins(t, d);						if(next(s, row, col, 0, 1, 1, 0, k, t)) T[last].ins(t, d);						if(next(s, row, col, 0, 1, 0, 1, k, t)) T[last].ins(t, d);						if(next(s, row, col, 0, 0, 1, 1, k, t)) T[last].ins(t, d);					}				}			}		}		swap(now, last);	}	int ret=0x3f3f3f3f;	for(int i=T[now].ihead; i; i=T[now].e[i].next) ret=min(ret, T[now].mn[T[now].e[i].to]);	return ret>=0x3f3f3f3f?0:ret-2;}int main() {	while(scanf("%d%d", &n, &m), n|m) {		for(int i=0; i