#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;
}

• Re:谁帮我看一下我的Dancing Links。。。总是TLE (17) chinaeli 2009-09-05 05:45:09
• Re:谁帮我看一下我的Dancing Links。。。总是TLE (75) tutest 2009-09-09 15:46:48
  • Re:谁帮我看一下我的Dancing Links。。。总是TLE (94) yizer 2009-09-29 20:20:59