hdu-1010 dfs+剪枝

时间:2022-05-12 07:04:53

思路:

剪枝的思路参考博客:http://www.cnblogs.com/zibuyu/archive/2012/08/17/2644396.html  在其基础之上有所改进

题意可以给抽象成给出一个图,让你求S点到D点之间是否存在一条长度为T的道路。求两地之间的距离用的是dfs,而dfs在这里的关键是找到回溯的条件,就是当到达D点并且剩余步数为0时,则符合题意的要求,由于我们只需要知道这样一条长度为T的路径是否存在,因此当我们发现存在的时候,只需要将一个全局flag给设置为1即可,然后从此之后的所有dfs调用都直接return。

另外关键的问题就是剪枝。当我们的思路走到求两个点的距离时,我们应当“俯视”一下——这两个点S和D,他们之间的距离从整个图上来看有什么性质。在这里有这样的规律:aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAI8AAADQCAIAAACx2aXmAAAHrElEQVR4nO2dPZKrOhBG7/bYCAW7IKCKRZAQsAMyEhbglIiUeLJZwA1Af0gCMQabDz7XCaZmQMZ91LK4r5v37/dnJCj8+/oVkHBoCwnaQoK2kDjWVlNEWTf/4Hol5XDKx3jVifP9tFfemNcZ1/34+zP+tpn5p0tznq05HF0epdVrjstZtmx5QoYTdSWvOomK9vsaPm2ry/WJnH3YlvHuW2ltXNJH14DL2Pr9GUNzqy/TKK4rEam8UVGTi1Jfplr0xPRviiiuW/mn6b3sa9hKrPkAkVifS3pUW0LM5Gn6ebLYT6erBarLpZjp63CWNFTx9PNQxVuZJTNm+oaL634cqlhdw1NtRVEUpVW5tsvoy9RIF+fPGm2m29IOWB7f5c4vITV1hiqOojhN4rp/1YlITWs9vOw32eHfW8vcMoKur4T9MpROGeLlHPZVJyJxzZXTeslEnzyZ1/bg3PLbkmzbkjkq9wJrtrpcrXLruSXOoq0QW1NcNm0twhe6Eq7cdW3ZMl/zLLkeH7U1f7GH2JL7vXmJU7sP+SeRUoYt5tZhtub9YcD3lnb/lHXmClnkIhWWIX4jt55ma46v+NjuXfW7QfFsGjVbzK3rsG7r/tAWEli2ng5tIUFbSNAWErSFBG0hQVtI0BYStIUEbSFBW0jQFhK0hQRtIUFbSNAWErSFBG0hQVtI0BYSn7elqv62SmLXW+GuNs4Nbb3qRDZpNcVagOYgeqJztXFuacuo0vWWXc6Vo0lW+Oby1ca5p61FOPoydfU3DlXZ/YxrK8/VxrmlraGKreisdJ16o3O1cWiLtr5tK3Dl2Y7O1ca5p61FODaaO/zRudo497S1Y8e8Hp2rjXNPW+P17mp5d0zOgbaQoC0kaAsJ2kKCtpCgLSRoCwnaQoK2kKAtJGgLiW/ZwvoX2/BxbmgLq55p139VuZctvHqmsHHuagutnmlfNcC9bAlgKmR2jkNbtHVZW5erZ+JKiFTPtG+cp9m6XD3Tg3fwAdEZv3FXy7tjcjS0hQRtIUFbSNAWErSFBG0hQVtI0BYStIUEbSFBW0jQFhLsO2bf8boqyOozPpULpPqMT+WSwQKoPuNTuWR0gOqZaIu2LmsLvPrsabawq8+eZgu7+uxxtsbr3dXy7picA20hQVtI0BYStIUEbSFBW0jQFhK0hQRtIUFbSNAWEuw7PnacG9rCqmd6cE8/Xj0Tn8qFVM/EZ9EAVcjwOU8XjDJt/cnW5eqZuBIi1TPxqVxQ9UwP3sEHRGf8xl0t747J0dAWErSFBG0hQVtI0BYStIUEbSFBW0jQFhK0hQRtIcFOVnayrquCrGfic55A6pn4nCcZLIB6Jj7nSUYHqEKGtmjrsrbA65meZgu7nulptrDrmR5na7zeXS3vjsk50BYStIUEbSFBW0jQFhK0hQRtIUFbSNAWErSFBG0hQVtI0BYStIUEbSFBW0jQFhK0hQRtIUFbSNAWErtsNYVZytrlX35K1XQNG6+pXLDNto7zNvwMVSxqDk36Mp2qRdtsOqDLpxGWgXKfu/85h2fbOuTpYzsK+YYq3n4jGWX3yOqa/S8Rh8lTm0V5I1SNv32ZOu3qtcCn27LeQF3fiqp3n+y32ua2J2NCs9DS75tqc1+X9V7L30tDS1vGKyQ479pae4/AZ3Orme4Jx0qbmzWmlVsqe9TVOnNLrGYaTSFirQTYlzrNGHVuU8hPvfhoH88tvWFGT52AUK5c3zzRln8NbXOTGZaUXRWn1UumkW4u2JZcCV1X22aRFoQuj6IorqvpAuK6H4cqSxNxwGIGfNSWCIoInJp6zuN3P+15dmYfc0wBeuBK6FzfnAd3ubaFyRs159psmhZyfoSPeZiteWvUl+kkrC/TpKxzr4C/PptbW0m2bG0LmF6LKWXmxy7sXYxjxzjnrv1BtGwzF56gzdEuW2pP0WZRUtbTxBHzyIFnJTQmmv45D8gt39Y5ZJune22K5R/mYfWwOuaKtsCmSbycJfp81YIzVLF71X3DlhkItey6ZtDyGJe85ZGR/4rXbG0uMr5Nh/4ba8KZH0r7IGYSGKMZey47fZ1Ly/TBtxbA3bbMq2wKfUvt1RC2g/fvCUNtqbfIxK5kjstihRmqLFVJlnVtZuncY6tvul7LWmNbaP/GludcSN63ZWSJI+5d7ttunH53vMuWcZb2sgYPWgn1I4tciFcz4FUny7Bo7/uX/2FDkC3tLti5bghhwRl9IF5blbmDNe9GHbNtPRXUbbi1fe/Ni7F/k5SDPP29EPFfdZGgLSRoCwnaQoK2kKAtJGgLCdpCgraQoC0kaAsJ2kKCtpCgLSRoCwnaQoK2kKAtJGgLCdpCgv1bxksVP81lXnbxkzYm+7fePP2I/q15nChvtOIndaRRSs3+rR2nn9W/Jd2s5Rb7t3aeflL/VptFy7pxT279sH9r7+mn9G9JW2tZyP4tVRT9p4YiLzv6t5LYCqXjG479W6NcSUJOP6N/q8uzbp74a31EMmvZv7V2+pbpI/q3NFt6A0DRjr/9axBJw/6t3aef0r/ltzVNWbHEsX9r5+mn9G/ptqrlVlutK+zf2nv6Kf1bjtySf1IroS6G/VtBnNK/5bUlN/Rx3bN/i6xCW0jQFhK0hcR/Hojviubvz7MAAAAASUVORK5CYII=" alt="" />

也就是一开始给我们的两个起始点S和D,如果他们之间距离的最小值的奇偶性和T的奇偶性是不同的,那么在一开始我们就可以判断——“NO”!因为0->0和1->1无论怎么走需要的步数都为偶数步,1->0或0->1无论怎么走需要的步数都为奇数步。利用这点,从一开始我们就可以进行奇偶剪枝。

还有一个并不影响最后AC但是也值得思考的一个剪枝,就是在一开始的时候给定图可走的点数就小于T,那就直接不需要考虑。


代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std; char G[][];//G[n][m]
int dx,dy;
int n,m,t;
int dir[][] = {{,-},{,},{,},{-,}};
int flag; void dfs(int cx,int cy,int step) {
//now we're at (cx,cy),there're "step" steps left to get to (dx,dy)
if(cx<||cx>n||cy<||cy>m)
return;
if(flag) return;
if(cx==dx&&cy==dy&&step==) {
flag = ;
return ;
}
for(int i = ;i < ;i++) {
int nx = cx+dir[i][];
int ny = cy+dir[i][];
if(nx<||ny<||nx>n||ny>m) continue;//(1)over-border
if(G[nx][ny] == 'X') continue;//(2)can't get to(nx,ny)
G[cx][cy] = 'X';
dfs(nx,ny,step-);
if(flag) return;
G[cx][cy] = '.';
}
} int main()
{
int sx,sy;
int i,j;
while(scanf("%d%d%d",&n,&m,&t)&&(n!=||m!=||t!=)) {
int wall = ;
for(i=;i<=n;++i)
{
scanf("%s",G[i]+);
for(j=;j<=m;++j)
{
if(G[i][j]=='S')
{
sx=i;
sy=j;
}
if(G[i][j]=='D')
{
dx=i;
dy=j;
}
if(G[i][j]=='X') wall++;
}
}
//cut branches-1
if((abs(sx-dx)+abs(sy-dy))% != t%) {
cout<<"NO"<<endl;
continue;
}
//cut branches-2
if(n*m-wall < t) {
cout<<"NO"<<endl;
continue;
}
flag = ;
dfs(sx,sy,t);
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}