题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110
结题报告:搜索中的一个重要的剪枝,现在记录下来,作为一个积累;
起点到终点的距离即sx-ex+sy-ey如果是奇数, 则题目中所给定的时间一定是只有奇数才可能得到结果,如果题目中的起点到终点的距离如果是偶数,则题目中给的时间如果是偶数才可能得到想要的结果。如何优化题目代码已经标记:
#include<cstdio> #include<cstring> using namespace std; const int maxn = 10; int n,m,t,step,flag; int dir[4][2]={0,-1,0,1,1,0,-1,0}; char mp[maxn][maxn]; int sx,sy,ex,ey; void dfs(int d,int r,int s) { if(d<0||d>=n||r<0||r>=m) return ; if(ex==d&&ey==r&&s==t) { flag = 1; return s; } for(int i=0;i<4;i++) { int xx=d+dir[i][0]; int yy=r+dir[i][1]; if(mp[xx][yy] != 'X') { mp[xx][yy]='X'; dfs(xx,yy,s+1); if(flag) return 1; mp[xx][yy]='.'; } } return s ; } int main() { int cnt ; while(scanf("%d %d %d",&n,&m,&t)!=EOF) { cnt=0; if(!(n || m || t)) break; for(int i=0;i<n;i++) { scanf("%s",mp[i]); for(int j=0;j<m;j++) { if(mp[i][j] == 'S') { sx=i; sy=j; } if(mp[i][j] == 'D') { ex=i; ey=j; } if(mp[i][j]=='X') cnt++; } } if(n*m-cnt<=t) { printf("NO\n"); continue; } int temp = t-(sx-ex+sy-ey); if(temp <0||temp%2)//一个重要的优化 { printf("NO\n"); continue; } flag = 0; mp[sx][sy]='X'; dfs(sx,sy,0); if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }
相关推荐
zoj 3663 Polaris of Pandora.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
Substitution cipher is defined by a substitution table assigning each character of the substitution alphabet another character of the same alphabet. The assignment is a bijection (to each character ...
zoj 1610 Count the Colors.md
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 1255 The Path.md
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
For the manager of a theatre, setting the price of a ticket is a rather delicate matter. Suppose that a theatre has n () seats, and that if you give away the tickets for free, all the seats will be ...
zoj 1810 The Gourmet Club.md
zoj 2151 The Highest Profits.md
zoj 2499 The Happy Worm.md
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·