首页 > 其他分享 >poj 2415(BFS)

poj 2415(BFS)

时间:2023-05-29 19:36:40浏览次数:44  
标签:include cur int pos BFS 棋子 poj 2415 maxn



题意: 有一种游戏,共有三个piece(不妨称为棋子),棋盘是由N个点构成的完全图,边有颜色。每次可以移动一个棋子,移动时必须满足棋子走过的边的颜色和其他两个棋子之间的连边的颜色一致。求把三个棋子移到同一个顶点的最少次数。


这道题是一个很简单的BFS,但为何一直TLE。。。。



#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 55;
struct node
{
	int pos[4];
	int move;
};
int n,p1,p2,p3;
char map[maxn][maxn];
bool vis[maxn][maxn][maxn];

int bfs()
{
	queue<node> q;
	node cur,nxt;
	cur.move = 0;
	cur.pos[1] = p1; cur.pos[2] = p2; cur.pos[3] = p3;
	q.push(cur);
	while(!q.empty()){
		cur = q.front();
		q.pop();
		if(cur.pos[1] == cur.pos[2] && cur.pos[2] == cur.pos[3]) return cur.move;
		for(int i = 1; i <= 3; i++)
			for(int j = 1; j <= n; j++){
				nxt.pos[1] = cur.pos[1]; nxt.pos[2] = cur.pos[2]; nxt.pos[3] = cur.pos[3];
				if(i == 1 && map[cur.pos[1]][j] == map[cur.pos[2]][cur.pos[3]]){
					if(vis[j][cur.pos[2]][cur.pos[3]] == true) continue;
					vis[j][cur.pos[2]][cur.pos[3]] == true;
					cur.pos[1] = j;
					nxt.move = cur.move + 1;
					q.push(nxt);
				}
				else if(i == 2 && map[cur.pos[2]][j] == map[cur.pos[1]][cur.pos[3]]){
					if(vis[cur.pos[1]][j][cur.pos[3]] == true) continue;
					vis[cur.pos[1]][j][cur.pos[3]] = true;
					cur.pos[2] = j;
					nxt.move = cur.move + 1;
					q.push(nxt);
				}
				else if(i == 3 && map[cur.pos[3]][j] == map[cur.pos[1]][cur.pos[2]]){
					if(vis[cur.pos[1]][cur.pos[2]][j] == true) continue;
					vis[cur.pos[1]][cur.pos[2]][j] = true;
					cur.pos[3] = j;
					nxt.move = cur.move + 1;
					q.push(nxt);
				}
			}
	}
	return -1;
}

int main()
{
	while(scanf("%d",&n) != EOF && n){
		scanf("%d%d%d",&p1,&p2,&p3);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				getchar();
				scanf("%c",&map[i][j]);
			}
		}
		memset(vis,false,sizeof(vis));
		int ans = bfs();
		if(ans == -1) printf("impossible\n");
		else printf("%d\n",ans);
	}
	return 0;
}



标签:include,cur,int,pos,BFS,棋子,poj,2415,maxn
From: https://blog.51cto.com/u_16143128/6373655

相关文章

  • poj 1054
    解题思路:这道题其实比较简单,就是找斜率相同且间距相同的点。首先,就是要找到两点,确定好斜率,然后就判断这两点是否在起始位置。其次,确定好斜率就确定了两个点之间的距离,如果某两点之间的间距不满足的话,那么这个点肯定不是这个方向上的。#include<iostream>#include<cstdio>#include......
  • poj 2010(优先队列)
    题意:奶牛大学:奶大招生,从C头奶牛中招收N头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。解题思路:这里要求最大中位数,中位数肯定是在这些人中间,故可以枚举中位数,可以先对分数进行排序,然后用二分去找最大中位数。每次枚举的中位......
  • poj 1948(搜索+剪枝)
    解题思路:这道题看到数据量,想到应该搜索+剪枝应该可以过。。可是别人的A了,我的却超时了。。。我用了一个mark[a][b],表示前两条边长度分别为a和b时,是否已经处理过,如果是的话就直接跳出。。。剩下的就是一个比较简单的搜索过程了,代码不难写,但是确实超时不可避免。。#include<iostream>......
  • poj 1604
    题意:计算n!最后一位不为0的数解题思路:1*2*3*......*n,每次乘完一个数后,把末尾0去掉,然后模上一个数,这样算出来的数肯定是最后一位不为0的数。。注意这里模的数不能太小,同时也不能太大,太小可能会影响乘积的效果,譬如可能出现0的情况被之前的模运算给抹掉了,太大就直接溢出了。。。参考了......
  • poj 2078(搜索+剪枝)
    解题思路:可以一行一行地递归求解,要是不符合条件就回溯,注意最后一行不能够移动它,因为可能会与之前重叠。。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=8;intn,mat[maxn][maxn],ans;intget_max(intdep){ intm=......
  • poj 1324(BFS+状态压缩)
    解题思路:这道题一开始的想法就是状态压缩,即考虑如何判重,由于蛇并非是直线的,所以想到了以每一个点的上下左右共四个值来表示相对位置。最开始想如何用四进制来表示它,无语。。。。。还是题目做少了,直接用两位来表示一个点即可(两位的二进制数可以表示0-3)。剩下的关键就是判断蛇头会不......
  • poj 1195(二维树状数组)
    解题思路:这是一道很裸的二维树状数组AC:#include<stdio.h>#include<string.h>#defineN1100intc[N][N],n,arr[N][N];intlowbit(intx){returnx&(-x);}voidupdate(intx,inty,intnum){inti,j;for(i=x;i<=n;i+=lowbit(i))for(j=y;......
  • POJ 1505(二分+贪心)
    题意:给一些书,这些书有不同的页数,让把这些书分成k份,必须是连续的,问这些份中页数和的最大值最小是多少。解题思路:知道了页数和的范围,而且书都是连续的,要找到页数和最大值的最小值可以直接二分答案。。AC:#include<iostream>#include<cstdlib>#include<cstring>usingnamespacestd......
  • poj 3411(DFS多点访问)
    题意:有n座城市和m(1<=n,m<=10)条路。现在要从城市1到城市n。有些路是要收费的,从a城市到b城市,如果之前到过c城市,那么只要付P的钱,如果没有去过就付R的钱。求的是最少要花多少钱。解题思路:这道题的n与m都很小,dfs可以搞定,但这里与以往的搜索不同,以前dfs每个节点只能够访问一次,这里有多次访......
  • POJ 1797 Heavy Transportation(迪杰斯特拉最短路变形)
    传送门题意分析:Hugo想要扩展他的公司,他有起重机要到目的地,到达目的地有很多条路径,但是,每一条路都有相应承重量,现在需要找出到达目的地的最大承重道路的承重质量。解题分析:首先,每一条路径的承重量取决于承重量最小的那条道路(短板效应),所以就是找所有路径的最小值,然后选择最小值最大的......