加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

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; ??? } }

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读