题目地址:https://ac.nowcoder.com/acm/problem/15434
自己的代码
#include<iostream>
#include<string.h>
using namespace std;
int n,p,q,beginX,beginY,endX,endY,tx,ty;//beginX,beginY:初始坐标 endX,endY:结束坐标
char map[505][505];//地图
bool book[505][505],flag;//book:做标记
int NEXT[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };//方向数组
void dfs(int x, int y) {
if (flag) {//如果已经找到路线则回溯时不再进行其他路线.
return;
}
if (x == endX && y == endY) {
flag = true;//做标记
return;
}
for (int i = 0; i <= 3; i++)
{
tx = x + NEXT[i][0];
ty = y + NEXT[i][1];
if (tx < 1 || tx>p || ty <1 || ty>q||map[tx][ty]=='x') {//判断是否越界和是否是障碍物
continue;
}
if (map[tx][ty] == '.' && book[tx][ty] == false) {
book[tx][ty] = true;
dfs(tx, ty);
book[tx][ty] = false;//回溯查看其他路线
}
}
}
int main()
{
cin >> n;
while (n--)
{
flag = false;
memset(map, '\0',sizeof(map));
memset(book, false, sizeof(book));
cin >> p >> q;
for (int i = 1; i <= p; i++) {
for (int j = 1; j <= q; j++) {
cin >> map[p][q];
if (map[p][q] == 's') {
beginX = p;
beginY = q;
}
if (map[p][q] == 't') {
endX = p;
endY = q;
}
}
}
dfs(beginX, beginY);
book[beginX][beginY] = true;
if (flag) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}