bfs求调
查看原帖
bfs求调
1044126
HaloCode楼主2024/10/26 17:11

考试的时候样例过了,再来一遍咋就不对了

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;
int T;
char dt[MAXN][MAXN];
bool bj[MAXN][MAXN] = {0};

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

struct Node {
	int x, y, d;
};

bool inMap(int x, int y, int n, int m) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
	cin >> T;
	
	while (T--) {
		int n, m, k;
		cin >> n;
		cin >> m;
		cin >> k;
		
		int sx, sy, sd;
		cin >> sx;
		cin >> sy;
		cin >> sd;
		
		for (int i = 1; i <= n; i++) {
			string s;
			cin >> s;
			for (int j = 0; j < m; j++) {
				dt[i][j + 1] = s[j];
			}
		}
		
		// bfs
		int head = 1, tail = 0, op = 0;
		Node dl[MAXN];
		dl[head].x = sx;
		dl[head].y = sy;
		dl[head].d = sd;
		bj[sx][sy] = 1;
		tail++;
		
		while (head <= tail && k > 0) {
			op = 0;
			Node cur = dl[head];
			int od = cur.d;
			int ox = cur.x + dx[od];
			int oy = cur.y + dy[od];
			
			if (inMap(ox, oy, n, m) && dt[ox][oy] == '.' &&!bj[ox][oy]) {
				tail++;
				dl[tail].x = ox;
				dl[tail].y = oy;
				dl[tail].d = od;
				bj[ox][oy] = 1;
			} else {
				op = 1;
				dl[tail].x = cur.x;
				dl[tail].y = cur.y;
				dl[tail].d = (od + 1) % 4;
			}
			
			if (op == 0) {
				head++;
			}
			k--;
		}
		
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (bj[i][j]) {
					cnt++;
				}
			}
		}
		
		cout << cnt << endl;
	}
	
	return 0;
}
2024/10/26 17:11
加载中...