首页 > 代码库 > hdu 1728
hdu 1728
#include <stdio.h>
#include <string.h>
#include <cmath>
char map[110][110];
bool sign[110][110];
int s_x, s_y, e_x, e_y;
bool flag;
int turn_step;
int dir[][2] = {0,-1, -1,0, 0,1, 1,0};
int n, m;
int x_num;
char str[110];
void dfs(int turn, int x, int y, int wan)
{
sign[x][y] = 1;
if(x==e_x && y == e_y)
{
if(wan <= turn_step)
flag = 1;
return ;
}
else if(flag) return;
else if(wan > turn_step) return;
else if (wan == turn_step && x !=e_x && y != e_y)
return ;
int tp_x = x, tp_y = y;
for(int i=0; i<4; i++)
{
tp_x = x + dir[i][0];
tp_y = y + dir[i][1];
if( !(tp_x >= n || tp_x<0 || tp_y>=m || tp_y<0 || map[tp_x][tp_y] == ‘*‘ || sign[tp_x][tp_y] == true) )
{
if( wan == turn_step && ((tp_x == e_x) || (tp_y == e_y)) )
{
if(turn != i) wan++;
dfs(i, tp_x, tp_y, wan);
sign[tp_x][tp_y] = 0;
if(turn != i) wan--;
}
else if(wan <turn_step)
{
if(turn != i) wan++;
dfs(i, tp_x, tp_y, wan);
sign[tp_x][tp_y] = 0;
if(turn != i) wan--;
}
}
}
return;
}
int i, j;
int main()
{
//freopen("read.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
//memset(map, ‘\0‘, sizeof(map) );
//memset(sign, 0, sizeof(sign) );
//x_num = 0;
scanf("%d%d", &n, &m);
for(i=0; i<n; i++)
{
scanf("%s", str);
for(j=0; j<m; j++)
{
map[i][j] = str[j];
}
}
scanf("%d%d%d%d%d", &turn_step, &s_y, &s_x, &e_y, &e_x);
s_x--; s_y--; e_x--; e_y--;
flag = 0;
dfs(-1, s_x, s_y, -1);
if(!flag) printf("no\n");
else printf("yes\n");
}
return 0;
}
来自为知笔记(Wiz)
附件列表
hdu 1728
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。