66分求助!!!
查看原帖
66分求助!!!
311110
_djc_楼主2022/7/12 09:12

请问这样写有什么错误吗为什么66分……

deque + bfs

求各位dalao帮忙QwQ

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
inline int read(){
    int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}
struct edge{
	int v, w, nxt;
}e[maxn];
int head[maxn], cnt;
void add(int u, int v, int w){
	e[++cnt] = {v, w, head[u]}, head[u] = cnt;
} 
int n, m;
char a1 = '\\', a2 = '/';
int vis[maxn], dis[maxn];
void bfs(){
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	deque<int> q;
	q.push_front(1), vis[1] = 1, dis[1] = 0;
	while(!q.empty()){
		int x = q.front(); q.pop_front();
		for(int i = head[x]; i; i = e[i].nxt){
			int y = e[i].v;
			if(vis[y]) continue;
			vis[y] = 1;
			int z = e[i].w;
			if(z == 0) q.push_front(y);
			else q.push_back(y);
			if(dis[y] > dis[x] + z) dis[y] = dis[x] + z;
		}
	}
}
int main() {
	n = read(), m = read();
	if((m + n) % 2){
		cout << "NO SOLUTION";
		return 0;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			char c;
			cin >> c;
			if(c == a1){
				add((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 0);
				add(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 1);
				add(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 0);
				add((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 1);
			}
			if(c == a2){
				add((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 1);
				add(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 0);
				add(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 1);
				add((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 0);
			}
		}
	}
	bfs();
	if(vis[(n + 1) * (m + 1)]) cout << dis[(n + 1) * (m + 1)];
	else cout << "NO SOLUTION";
}
2022/7/12 09:12
加载中...