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.
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.
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
又是迷宫逃生问题，且门只能在第T秒打开。
剪枝中的奇偶剪枝
image.png
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10
using namespace std;
bool flag,ans,visited[N][N];
int n,m,t,xe,ye;
char map0[N][N];
void dfs(int x,int y,int timen){
if(flag) return ;
if(timen>t) return ;
if(x<0||x>n-1||y<0||y>m-1) return ;
if(timen==t&&map0[x][y]=='D') {flag=ans=true;return ;}
int temp=t-timen-abs(xe-x)-abs(ye-y);
if(temp&1) return ;//奇偶剪枝
if(!visited[x-1][y]&&map0[x-1][y]!='X'){
visited[x-1][y]=true;
dfs(x-1,y,timen+1);
visited[x-1][y]=false;
}
if(!visited[x+1][y]&&map0[x+1][y]!='X'){
visited[x+1][y]=true;
dfs(x+1,y,timen+1);
visited[x+1][y]=false;
}
if(!visited[x][y-1]&&map0[x][y-1]!='X'){
visited[x][y-1]=true;
dfs(x,y-1,timen+1);
visited[x][y-1]=false;
}
if(!visited[x][y+1]&&map0[x][y+1]!='X'){
visited[x][y+1]=true;
dfs(x,y+1,timen+1);
visited[x][y+1]=false;
}
}
int main(){
int xs,ys;
while(scanf("%d%d%d",&n,&m,&t)!=EOF&&(n||m||t)){
int cnt=0;
getchar();
memset(visited,false,sizeof(visited));
flag=ans=false;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>map0[i][j];
if(map0[i][j]=='S'){
xs=i;ys=j;
visited[i][j]=true;
}
if(map0[i][j]=='D'){
xe=i;ye=j;
}
if(map0[i][j]=='X'){
cnt++;
}
}
}
if(n*m-cnt-1>=t) dfs(xs,ys,0);
if(ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
迷宫型的动态规划。
由题意的不可接触对角线但可接触对角线的规则可知，
对角线上半部分每个格子只能从左边的格子与上面的格子走来，对角线上的格子只能从上边的格子走来。则路径数的状态转移过程为
对角线上的格子：d[i][i]=d[i-1][i];
对角线外的格子：d[i][j]=d[i-1][j]+d[i][j-1]；
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n;
long long map[40][40];
int main()
{
int i,j,cnt=1;;
while(cin>>n&&n!=-1)
{
memset(map,0,sizeof(map));
for(i=0;i<=n;++i)
map[0][i]=1;
for(i=1;i<=n;++i)
for(j=0;j<=i;++j)
{
if(i==j)
map[i][j]=map[i][j-1];
else
map[i][j]=map[i-1][j]+map[i][j-1];
}
printf("%d %d %I64d\n",cnt++,n,2*map[n][n]);
}
return 0;
}
网友评论