HDOJ--1010题C++
发布时间:2020-12-16 10:49:14 所属栏目:百科 来源:网络整理
导读:有两点需要注意,第一点就是,题意是指在第T秒时门才打开,并不是越早到门口就能越早出去,而是只要存在指定长的路径即可以出去。 第二点,每次深搜发现答案不符都必须将点重新初始化。 #includeiostream #includeutility #define INF 10000 using namespace
有两点需要注意,第一点就是,题意是指在第T秒时门才打开,并不是越早到门口就能越早出去,而是只要存在指定长的路径即可以出去。
第二点,每次深搜发现答案不符都必须将点重新初始化。
#include<iostream> #include<utility> #define INF 10000 using namespace std; char maze[100][7]; int d[100][7]; int n,m,t,start_i,start_j,end_i,end_j; int dx[]= {0,1,-1},dy[]= {1,-1,0}; bool dfs(int i,int j); int main() { ??? while(cin>>n>>m>>t && n &&m ??????????? && t) ??? { ??????? for(int i=0; i<n; i++) ??????????? for(int j=0; j<m; j++) ??????????? { ??????????????? cin>>maze[i][j]; ??????????????? if(maze[i][j]==‘S‘) ??????????????? { ??????????????????? start_i=i; ??????????????????? start_j=j; ??????????????? } ??????????????? if(maze[i][j]==‘D‘) ??????????????? { ??????????????????? end_i=i; ??????????????????? end_j=j; ??????????????? } ??????????? } ??????? for(int i=0; i<n; i++) ??????????? for(int j=0; j<m; j++) ??????????????? d[i][j]=INF; ??????? d[start_i][start_j]=0; ??????? if(dfs(start_i,start_j)) ??????????? cout<<"YES"<<endl; ??????? else ??????????? cout<<"NO"<<endl; ??? } ??? return 0; } bool dfs(int i,int j) { ??? if(i==end_i && j==end_j) ??? { ??????? if(d[i][j]==t) ??????? { ??????????? d[i][j]=INF; ??????????? return true; ??????? } ??????? else ??????? { ??????????? d[i][j]=INF; ??????????? return false; ??????? } ??? } ??? else ??? { ??????? for(int k=0; k<4; k++) ??????? { ??????????? int nx=dx[k]+i,ny=dy[k]+j; ??????????? if( nx>=0 &&nx < n &&ny>=0 && ny<m && (d[nx][ny]==INF) &&((maze[nx][ny]==‘.‘)||(maze[nx][ny]==‘D‘))) ??????????? {
??????????????????? d[nx][ny]=d[i][j]+1; ??????????????????? if(dfs(nx,ny)) ??????????????????? { ??????????????????????? d[nx][ny]=INF; ??????????????????????? return true; ??????????????????? } ??????????????????? else ??????????????????????? d[nx][ny]=INF; ??????????? } ??????? } ??????? d[i][j]=INF; ??????? return false; ??? } }
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |