问题标题: 酷町堂：2147 危险的森林

2147   危险的森林

经验值：800 时间限制：1000毫秒

题目描述 Description

一个面积为n * n的森林，里面布满了陷阱，每个陷阱有2种状态：s和d。前者表示陷阱已经被破坏，后者表示陷阱正常。现在探险家伊泽处在森林中的某个位置，他每次只能移动到上、下、左、右这四个方向之一的相邻位置上，伊泽想要从点A走到点B，但是伊泽不能走出森林，请你写个程序，判断伊泽能不能办到。如果起点或者终点有一个布置有正常的陷阱(状态为d)，则看成无法办到。

输入描述 Input Description

第1行是测试数据的组数k。
每组测试数据的第一行数一个正整数n (1 <= n <= 100)，表示森林的面积是n * n的。
接下来输入n * n的矩阵，矩阵中的元素为s或者d。
再接下来一行是4个整数a, b,c, d，描述A处在第a行, 第b列，B处在第c行, 第d列。
注意：a,b,c,d都是从1开始计数的。

输出描述 Output Description

能办到则输出“YES”，否则输出“NO”。

样例输入 Sample Input

2 3 sdd ssd dss 1 1 2 2 5 sssss dddsd ssdss dddss sssds 1 1 4 1

样例输出 Sample Output

YES NO

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int n, a, b, c, d;
string s;
bool G[10][10];
bool vis[10][10];
bool flag = false;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int x, int y) {
	if (x == c && y == d) {
		flag = true;
		return ;
	}
	for (int i = 0; i < 4; i ++) {
		int nx = x + dir[i][0], ny = y + dir[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && G[nx][ny] && !vis[nx][ny]) {
			vis[nx][ny] = true;
			dfs(nx, ny);
			vis[nx][ny] = false;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	int k;
	cin >> k;
	for (int i = 1; i <= k ;i ++) {
		cin >> n;
		for (int j = 1; j <= n; j ++) {
			cin >> s;
			for (int k = 0; k < s.size(); k ++) {
				if (s[j] == 's') {
					G[j][k + 1] = true;
				}
			}
		}
		cin >> a >> b >> c >> d;
		vis[a][b] = true;
		dfs(a, b);
		vis[a][b] = false;
		if (flag == true) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

样例没过，搞不懂哪错了

张恩泽在2021-05-04 23:04:56追加了内容

顶！

张恩泽在2021-05-05 07:27:21追加了内容

再顶！！！！

张恩泽在2021-05-05 13:18:48追加了内容

顶！！！

张恩泽在2021-05-05 14:43:34追加了内容

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, a, b, c, d;
string s;
bool G[10][10];
bool vis[10][10];
bool flag = false;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int x, int y) {
	if (flag == true) {
		return ;
	}
	if (x == c && y == d) {
		flag = true;
		return ;
	}
	for (int i = 0; i < 4; i ++) {
		int nx = x + dir[i][0], ny = y + dir[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && G[nx][ny] && !vis[nx][ny]) {
			vis[nx][ny] = true;
			dfs(nx, ny);
			vis[nx][ny] = false;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	int k;
	cin >> k;
	for (int i = 1; i <= k ;i ++) {
		cin >> n;
		for (int j = 1; j <= n; j ++) {
			cin >> s;
			for (int k = 0; k < s.size(); k ++) {
				if (s[j] == 's') {
					G[j][k + 1] = true;
				}
			}
		}
		cin >> a >> b >> c >> d;
		vis[a][b] = true;
		dfs(a, b);
		vis[a][b] = false;
		if (flag == true) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		flag = false;
		memset(vis, false, sizeof(vis));
		memset(G, false, sizeof(G));
	}
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

感觉用memset有些怪，但样例还是没过

@黄依成

张恩泽在2021-05-05 18:28:13追加了内容

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, a, b, c, d;
string s;
bool G[10][10];
bool vis[10][10];
bool flag = false;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int x, int y) {
	if (flag == true) {
		return ;
	}
	if (x == c && y == d) {
		flag = true;
		return ;
	}
	for (int i = 0; i < 4; i ++) {
		int nx = x + dir[i][0], ny = y + dir[i][1];
		//cout << nx << ' ' << ny << endl;
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && G[nx][ny] && !vis[nx][ny]) {
			vis[nx][ny] = true;
			dfs(nx, ny);
			vis[nx][ny] = false;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	int k;
	cin >> k;
	for (int i = 1; i <= k ;i ++) {
		cin >> n;
		for (int j = 1; j <= n; j ++) {
			cin >> s;
			for (int k = 0; k < s.size(); k ++) {
				if (s[k] == 's') {
					G[j][k + 1] = true;
				}
			}
		}
//		for (int j = 1; j <= n; j ++) {
//			for (int k = 1; k <= n; k ++) {
//				cout << G[j][k] << ' '; 
//			}
//			cout << endl;
//		}
		cin >> a >> b >> c >> d;
		vis[a][b] = true;
		dfs(a, b);
		vis[a][b] = false;
		if (flag == true) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		flag = false;
		memset(vis, false, sizeof(vis));
		memset(G, false, sizeof(G));
	}
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

调试了一下，样例过了，但wa了