hdu 1010(dfs+剪定)

http://acm.hdu.edu.cn/showproblem.php?pid=1010
この問題はちょうどt時間に到着することです.t時間内に到着するわけではありません.
アイデア:剪定+dfs
最初の剪定は、残りの歩数が残りの時間より大きいとき、犬は通れないと考えられます.
 
次に二つ目の剪定をします.
私たちはmapのパリティを01番で表します.
0 1 0 1 0 1 0 1 1 1 
1 0 1 0 1 0 1 0 0 
0 1 0 1 0 1 0 1 1 1 
1 0 1 0 1 0 1 0 0 
0 1 0 1 0 1 0 1 1 1 
私達は0から1歩歩いて必ず1まで歩いて、1から1歩歩いてきっと0まで歩くことを発見します.
つまり、現在の犬の位置の座標がDの座標と奇偶性と異なる場合、犬は奇数歩を歩かなければなりません.
同じように、犬の位置座標がDの座標パリティと同じであれば、犬は偶数ステップ数を歩かなければなりません.
 
つまり、犬の座標x、yと2のとり残しはそのパリティであり、Dxyと2のとり残しはDのパリティである.
二つのパリティを加えてもう2に取って、この残りの数を持って行ったら残りの時間と2に取った残りの数を比較すればいいです.
 
注意してください.私が問題をしている間に、枝を切ってから、タイムアウトの現象を発見しました.いろいろ考えましたが、以前書いたdfsの欠点です.以前は注意していませんでした.これからは注意が必要です.

#include<iostream>

#include<math.h>

using namespace std;

char s[10][10];

int ax,ay,bx,by,n,m,k;

int t[4][2]={1,0,-1,0,0,1,0,-1},vist[10][10],flag;

void dfs(int x,int y,int count)

{

	int i,mx,my;

	if(x==bx&&y==by)

	{

		if(k==count)

			flag=1;

		return;

	}

	if(count>=k)

		return;

	if(s[x][y]!='X')

	{

		for(i=0;i<4;i++)

		{

			mx=x+t[i][0];

			my=y+t[i][1];

			if(s[mx][my]!='X'&&mx>=1&&mx<=n&&my>=1&&my<=m&&!vist[mx][my])

			{

				vist[mx][my]=1;

				dfs(mx,my,count+1);

				vist[mx][my]=0;

				if(flag)                       //  ，        ，      ！    dfs ，      

					return;

			}

		}

	}

}

int main()

{

	while(scanf("%d%d%d",&n,&m,&k)>0&&(n+m+k))

	{

		int i,count;

		for(i=1;i<=n;i++)

		{

			getchar();

			for(int j=1;j<=m;j++)

			{

				scanf("%c",&s[i][j]);

				if(s[i][j]=='S')

				{

					ax=i;

					ay=j;

				}

				if(s[i][j]=='D')

				{

					bx=i;

					by=j;

				}

			}

		}

		getchar();

		memset(vist,0,sizeof(vist));

		if(abs(ax-bx)+abs(ay-by)>k||(ax+bx+ay+by+k)%2==1)            //  

		{

			printf("NO
");

			continue;

		}

		vist[ax][ay]=1;

		flag=0;

		count=0;

		dfs(ax,ay,count);

		if(flag==1)

			printf("YES
");

		else

			printf("NO
");

	}

	return 0;

}