社区讨论

蒟蒻刚学OI求助??

P2199最后的迷宫参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi7ycz3j
此快照首次捕获于
2025/11/21 05:37
4 个月前
此快照最后确认于
2025/11/21 05:37
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int v[300][300];
char a[300][300];
int step[300][300];
int n,m;
int xp[4] = {0, 0, 1, -1};
int yp[4] = {1, -1, 0, 0};
void bfs(int x,int y,int fx,int fy) {
	v[x][y] = 1;
	int xx,yy,hx,hy;
	queue<int>sx;
    queue<int>sy;
	sx.push(x);
	sy.push(y);
	while(!sx.empty()){
		hx = sx.front();sx.pop();
		hy = sy.front();sy.pop();
        for(int i = 0;i < 4 ; i ++){
        	xx = hx + xp[i];
        	yy = hy + yp[i];
        	if(xx >=1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == 'O' && !v[xx][yy])
        		sx.push(xx);
        		sy.push(yy);
        		v[xx][yy] = 1;
        		step[xx][yy] = step[hx][hy] + 1;
        		int stepx,stepy;
        		stepx = xx;	stepy = yy;
        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]) {
        	    	stepx --; stepy ++;//东北
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }
        		stepx = xx;	stepy = yy;
        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m  && !v[stepx][stepy]){
        	    	stepx --;//北
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }
        		stepx = xx;	stepy = yy;
        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m &&  !v[stepx][stepy]){
        	    	stepx --; stepy --;//西北
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        		
        	    }	
        		stepx = xx;	stepy = yy;

        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]){
        	    	 stepy --;//西
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }	
        		stepx = xx;	stepy = yy;

        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]){
        	    	stepx ++; stepy --;//西南
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }	
        		stepx = xx;	stepy = yy;

        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]){
        	    	 stepx ++;//南
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }	
        		stepx = xx;	stepy = yy;

        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]){
        	    	stepx ++; stepy ++;//东南
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }	
        		stepx = xx;	stepy = yy;

        	    while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n &&  stepy <= m && !v[stepx][stepy]){
        	    	stepy ++;//东
        	    	if(stepx == fx && stepy == fy){
        	    		cout << step[xx][yy] <<endl;
        	    		return;
        	    	}
        	    }	
			}
        }
	cout << "Poor Harry" << endl;
	return;
}
int main(){
	int sx, sy, fx, fy;
	cin >> n >> m;
	for(int i = 1;i <= n; i ++){
		for(int j = 1;j <= m ; j ++){
			cin >> a[i][j];
		}
	}
	while(scanf("%d%d%d%d", &fx, &fy, &sx, &sy)) {
		if(fx == 0) break;
		bfs(sx, sy, fx, fy);
	}
	return 0;
}
纯暴力过不了样例 QAQ

回复

1 条回复,欢迎继续交流。

正在加载回复...