hdu1010Tempter of the Bone深搜剪枝
感冒还没还利索，脑子不怎么转个，尤其是这半周没好好刷题愧疚得导致今天早上4点就醒了==一上午也才研究明白这么一个，不过弄懂了奇偶剪枝我还是很开心的
简单的说，奇偶剪枝根据未走步子和规定步数的奇偶关系减少循环次数的。说的有点迷糊，拿这个题来说要求只能走T步，从当前点到终点的步数要和剩余能走的步数奇偶一致。
怎么求当前点到终点步子的奇偶呢，这个很明显是和当前点到终点最短距离奇偶一样的*^_^*
Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 86211 Accepted Submission(s): 23511
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output
NO YES
//用 scanf 输入的请况 ,注意getchar(); 或则去除scanf和getchar(); 用cin也能AC
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t;
char Maze[8][8];
int di[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int sum;
int st,st1,ed,ed1;
int flag;
int abs(int x)
{
return x>0?x:-x;
}
void dfs(int x,int y,int e)
{
if(x>n||x<1||y>m||y<1) return;
if(x==ed&&y==ed1&&e==t)
{
flag=1;
return;
}
if(flag==1) return;
if((abs(x-ed)+abs(y-ed1)-(t-e))%2!=0) return;//之前这里笔误写成st st1了说到底还是没好好理解懂剪枝本质
for(int i=0;i<4;i++)
{
int xx=di[i][0]+x,yy=di[i][1]+y;
if(xx>n||xx<1||yy>m||yy<1) continue;
if(Maze[xx][yy]!='X')
{
Maze[xx][yy]='X';
dfs(xx,yy,e+1);
Maze[xx][yy]='.';
}
}
return ;
}
int main()
{
// freopen("cin.txt","r",stdin);
int i,j;
while(scanf("%d%d%d",&n,&m,&t)==3&&(n+m+t))
{
sum=0;
flag=0;
getchar();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%c",&Maze[i][j]);
// cin>>Maze[i][j];
if(Maze[i][j]=='S')
{
st=i;
st1=j;
Maze[i][j]='X';
}
else if(Maze[i][j]=='D')
{
ed=i;
ed1=j;
sum++;
}
else if(Maze[i][j]=='.')
sum++; //标记能够走的步数
}
getchar();
}
if(sum>=t&&t>=abs(ed1-st1)+abs(ed-st)&&(abs(ed-st)+abs(ed1-st1)-t)%2==0)
dfs(st,st1,0);
if(flag==1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
查看18道真题和解析
