(悬关)萌新第一天学c艹,dfs22pts(阳历全过)在线求条
查看原帖
(悬关)萌新第一天学c艹,dfs22pts(阳历全过)在线求条
1072631
_MRzeng_楼主2025/8/2 09:56

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int n , m;
char c[N][N];
bool mark[N][N];
int sx , sy , ex , ey;
bool flag = false;
char k , lastk;
int minn = 1919810;
int d[4][2] = {0 , 1 , 0 , -1 , 1 , 0 , -1 , 0};
void dfs(int x , int y , int cnt){
//	cout << cnt << "\n";
//	cout << x << " " << y << "\n";
//	cout << k << " " << lastk << "\n\n";
	mark[x][y] = 1;
	if(x == ex && y == ey){
		flag = true;
		if(cnt > minn) k = lastk;
		if(cnt <= minn) minn = cnt;
		return ;
	}
	if(c[x][y] == '.') return ;
	if(cnt == 0){
		for(int i = 0 ; i < 4 ; i++){
			int dx = x + d[i][0];
			int dy = y + d[i][1];
//			cout << dy << "\n";
			if(dx < 1 || dy < 1 || dx > n || dy > m || mark[dx][dy] == 1) continue;
			if(i == 0) lastk = k , k = 'E';
			if(i == 1) lastk = k , k = 'W';
			if(i == 2) lastk = k , k = 'S';
			if(i == 3) lastk = k , k = 'N';
			dfs(dx , dy , cnt + 1);
		}		
	}
	else{
//		cout << 91 << "\n\n";
		if(c[x][y] == '^') dfs(x - 1 , y , cnt + 1);
		mark[x - 1][y] = 0;
		if(c[x][y] == 'v') dfs(x + 1 , y , cnt + 1);
		mark[x + 1][y] = 0;
		if(c[x][y] == '>') dfs(x , y + 1 , cnt + 1);
		mark[x][y + 1] = 0;
		if(c[x][y] == '<') dfs(x , y - 1 , cnt + 1);
		mark[x][y - 1] = 0;
	}
}
signed main(){
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin >> c[i][j];
			if(c[i][j] == 'o') mark[i][j] = 1 , sx = i , sy = j;
			if(c[i][j] == 'x') ex = i , ey = j;
			if(c[i][j] == '.') mark[i][j] = 1;
		}
	}
	dfs(sx , sy , 0);
	if(!flag) return cout << ":(" , 0;
	cout << ":)\n" << k; 
    return 0;
}
2025/8/2 09:56
加载中...