奋战杭电ACM（DAY6）1010

本文主要是介绍奋战杭电ACM（DAY6）1010，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

纠结了两天的题，一开始自己想不出来，上网搜前辈的解题报告，没看懂……

对算法掌握太少了，知道知识点是深度优先遍历（DFS）和剪枝（本题特殊在奇偶剪枝），于是花了一天的时间学习这两个知识点，到处翻书哇！！于是还是没做出来……但是又结合前辈的解题报告，这次能看懂了！！

然后自己做，失败2次……第三次解决了！！提交，一次AC！！

作对这道题成就感胜过昨天AC4到啊！！

总结一下，本题的思路还是很明确的，DFS出所有走法，再根据条件剪枝，优化，减少时间空间损耗。

Tempter of the Bone

#include <iostream>
#include <string>
#include <cmath>
using namespace std;int N,M,T,end_i,end_j;
bool visited[6][6],res;//因为1<N,M<7，所以开到6就可以
char maze[6][6];void DFS(int i, int j, int t)
{if(res) return;//吭哧吭哧剪枝ing……if(t>T) return;if(i<0 || i>=N || j<0 || j>=M) return;int temp;temp= abs(i-end_i)+abs(j-end_j);if((T-t-temp) & 1) return;//奇偶剪枝if(t==T && maze[i][j]=='D'){res=true; return;}if(!visited[i-1][j] && maze[i-1][j]!='X')//DFS出所有走法……四个方向~~{visited[i-1][j]=true;//如下DFS(i-1, j, t+1);visited[i-1][j]=false;//这两步很巧妙！！}if(!visited[i+1][j] && maze[i+1][j]!='X'){visited[i+1][j]=true;DFS(i+1, j, t+1);visited[i+1][j]=false;}if(!visited[i][j-1] && maze[i][j-1]!='X'){visited[i][j-1]=true;DFS(i, j-1, t+1);visited[i][j-1]=false;}if(!visited[i][j+1] && maze[i][j+1]!='X'){visited[i][j+1]=true;DFS(i, j+1, t+1);visited[i][j+1]=false;}
}int main()
{while(cin >> N >> M >> T && (N || M || T))//这次还学到了bool型的用法，节省了不少！！{int i,j,k=0,s_i,s_j,min;memset(visited, false, sizeof(visited));//这个也很新颖，一次性全部赋值，头文件<string>for(i=0; i<N; i++){for(j=0; j<M; j++){cin >> maze[i][j];if(maze[i][j]=='S'){s_i=i; s_j=j; visited[i][j]=true;}if(maze[i][j]=='D'){end_i=i; end_j=j;}if(maze[i][j]=='X')k+=1;}}res=false;min=abs(s_i-end_i) + abs(s_j-end_j);if(abs(min-T)%2==0 && min<=T && (N*M-k-1>=T))//各种剪枝~~~^O^DFS(s_i,s_j,0);if(res)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

这篇关于奋战杭电ACM（DAY6）1010的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---