Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
谁帮我看一下我的Dancing Links。。。总是TLE#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; struct Element { bool head; Element *up , *down , *left , *right; bool line; Element *top; Element *ans; int name; Element() { head = false; line = false; up = down = left = right = top = ans = NULL; } }; int X , Y; bool answer; bool mp[400][400]; Element *head; Element *Line[400]; Element *Row[400]; Element *Tp[400]; Element *Lt[400]; Element *ans[400]; void DEL_LINE(Element *&p) { p->left->right = p->right; p->right->left = p->left; for (Element * r = p->down;r!=p;r = r->down) { for (Element * q = r->right;q!=r;q=q->right) { q->up->down = q->down; q->down->up = q->up; } } } void RES_LINE(Element *&p) { p->left->right = p; p->right->left = p; for (Element * r = p->down;r!=p;r = r->down) for (Element * q = r->right;q!=r;q=q->right) { q->up->down = q; q->down->up = q; } } void DFS(int deep) { if (answer) return; if (head->right == head) { answer = true; } else { Element *p = head->right; if (p->down == p) return; else { DEL_LINE(p); for (Element *r = p->down;r!=p;r = r->down) { ans[deep] = r; for (Element *q = r->left;q!=r;q=q->left) if (!q->line) DEL_LINE(q->top); DFS(deep+1); for (Element *q = r->left;q!=r;q=q->left) if (!q->line) RES_LINE(q->top); } RES_LINE(p); if (answer) return; } } } int main() { freopen("data.in","r",stdin); while (scanf("%d%d",&X,&Y)!=EOF) { memset(Line,0,sizeof(Line)); memset(Row,0,sizeof(Row)); memset(mp,0,sizeof(mp)); memset(Tp,0,sizeof(Tp)); memset(Lt,0,sizeof(Lt)); memset(ans,0,sizeof(ans)); answer = false; head = new Element; head->head = true; for (int i=0;i<X;i++) for (int j=0;j<Y;j++) { int tmp; scanf("%d",&tmp); mp[i][j] = tmp; } for (int i=0;i<X;i++) { Element *p = new Element; p->line = true; p->ans = p; p->name = i; if (i) { p->up = Row[i-1]; Row[i-1]->down = p; } else { p->up = head; head->down = p; } Row[i] = Lt[i] = p; } Row[X-1]->down = head; head->up = Row[X-1]; //------------------------------ for (int i=0;i<Y;i++) { Element *p = new Element; p->line = true; p->top = p; p->name = i; if (i) { p->left = Line[i-1]; Line[i-1]->right = p; } else { p->left = head; head->right = p; } Line[i] = Tp[i] = p; } Line[Y-1]->right = head; head->left = Line[Y-1]; //---------------------------------- for (int i=0;i<X;i++) for (int j=0;j<Y;j++) if (mp[i][j]) { Element *p = new Element; p->top = Tp[j]; p->ans = Lt[i]; p->up = Line[j]; p->left = Row[i]; Line[j]->down = Row[i]->right = p; Line[j] = Row[i] = p; } for (int i=0;i<Y;i++) Line[i]->down = Tp[i],Tp[i]->up = Line[i]; for (int i=0;i<X;i++) Row[i]->right = Lt[i],Lt[i]->left = Row[i]; DFS(0); if (answer) puts("Yes, I found it"); else puts("It is impossible"); } return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator