求助!! TLE了
查看原帖
求助!! TLE了
519573
Daniel_yao楼主2022/2/12 21:51
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
char a[N][N];
int n, m, sx, sy, fx, fy;
bool map_[N][N], tmp[N][N];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};

inline int read()
{
    register int x = 0, t = 1;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*t;
}


void dfs(int x, int y){
	if(x == fx && y == fy){
		cout << "Yes";
		exit(0);
	}
	for(int i = 0;i <= 3;i++){
		int x_ = x + dx[i];
		int y_ = y + dy[i];
		if(x_ >= 1 && x_ <= n && y_ >= 1 && y_ <= m && tmp[x_][y_] == 0 && map_[x_][y_] == 0){
			tmp[x_][y_] = 1;
			dfs(x_, y_);
			tmp[x_][y_] = 0;
		}
	}
}

int main(){
	n = read();
	m = read();
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> a[i][j];
			if(a[i][j] == '#'){
				map_[i][j] = 1;
			}
			if(a[i][j] == 's'){
				sx = i, sy = j;
			}
			if(a[i][j] == 'g'){
				fx = i, fy = j;
			}
		}
	}
	tmp[sx][sy] = 1;
	dfs(sx,sy);
	cout << "No" << endl;
	return 0;
}

2022/2/12 21:51
加载中...