AOJ 6.Hero In Maze

157

简单的最短路 BFS DFS都可以实现(BFS应该会更快一点吧)

其中输入的N、M、T中,N是列,M是行,而不是和大多数题目一样,N是行,M是列

另外,类中不要乱放常量,类中不要直接为类变量赋初值(不是所有编译器都承认貌似~)



#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define REP(n) for(int o=0;o<n;o++)

const int maxn = 25;
const int delta[4] = {0,0,1,-1};

class LOVE {
private:
int N,M,T;
int x1,y1,x2,y2;
bool visited[maxn][maxn];//是否已访问过该位置
char map[maxn][maxn];//地图
int ans;//结果


void dfs(int x,int y,int l) {
if(x < 0 || y < 0 || x >= M || y >= N ||
visited[x][y] == true || map[x][y] == '*')
return;
if(x == x2&&y == y2)
ans = l;

visited[x][y] = true;

for(int i = 0;i < 4;i++)
dfs(x + delta[i],y + delta[3 - i],l + 1);

}

public:
bool Do() {
scanf("%d%d%d",&N,&M,&T);
//测试数据结束
if(N == 0 && M == 0 && T == 0)
return false;
//输入地图
for(int i = 0;i < M;i++) {
for(int j = 0;j < N;j++) {
char temp;
scanf("\n%c\n",&temp);
if(temp == 'S') {
x1 = i;
y1 = j;
temp = '.';
}
if(temp == 'P') {
x2 = i;
y2 = j;
temp = '.';
}
map[i][j] = temp;
}
}

//输出地图
/*
for(int i = 0;i < M;i++) {
for(int j = 0;j < N;j++)
printf("%c",map[i][j]);
printf("\n");
}
printf("\n");
*/

//初始化
ans = -1;
memset(visited,false,sizeof(visited));
//dfs寻求最短路(用bfs应该会更快点,不过数据小,就不改了)
dfs(x1,y1,0);

/*
for(int i = 0;i < M;i++) {
for(int j = 0;j < N;j++)
printf("%d",visited[i][j]);
printf("\n");
}
printf("\n");
*/

printf("%s\n",ans == -1 || ans > T ? "NO" : "YES");

return true;
}
};



int main() {
LOVE LIVE;
while(LIVE.Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论