（广度优先搜索、走迷宫）BJTUOJ #1194 Maze Problem #1191 Satellite Photographs #1192 Prime Path

原题链接 1194 - Maze Problem - acm.bjtu

翻译一下就是输入t个大小为n*m的迷宫，S表示起点，E表示终点，-表示空地，#表示墙，输出从起点到终点的最短路径，如果无法到达终点就输出-1

因为需要找到最短路径，所以考虑广度优先搜索

先从起点搜索四个方向找所空地标记为一步能到达的空地，在从n步能到的空地搜索四个方向找所有n步不能到达的空地标记为n+1步能到达的空地，如果找到了终点就输出到达终点消耗的步数，如果在某次搜索时已经找不到任何未到达过的空地却仍然没有找到终点，则说明无法到达终点

算法时间复杂度为o(n*m)

#include 
#include 
int main(int argc, char *argv[]) {
	int a,n,m,t=0,maze[100][100],i,j,st[2],en[2],endl,endmove,flag,pos[10000][2],dist;
	char c[101];
	scanf("%d",&a);
	while(t0&&maze[pos[i][0]-1][pos[i][1]]==1)
				{
					if(en[0]==pos[i][0]-1&&en[1]==pos[i][1])
					{
						flag=1;
						break;
					}
					maze[pos[i][0]-1][pos[i][1]]=0;
					pos[endmove][0]=pos[i][0]-1;
					pos[endmove][1]=pos[i][1];
					endmove++;
				}
				if(pos[i][0]0&&maze[pos[i][0]][pos[i][1]-1]==1)
				{
					if(en[0]==pos[i][0]&&en[1]==pos[i][1]-1)
					{
						flag=1;
						break;
					}
					maze[pos[i][0]][pos[i][1]-1]=0;
					pos[endmove][0]=pos[i][0];
					pos[endmove][1]=pos[i][1]-1;
					endmove++;
				}
				if(pos[i][1] 
原题链接 1191 - Satellite Photographs - acm.bjtu​​​​​
 
输入一个w*h的图片，*代表农场区域，.表示非农场区域，输出最大的连续农场区域
 
类似的迷宫题，只不过不计算走的步数，而是计算搜索到的区域的面积，没有终点，每次都需要搜索直到没有未搜索过的区域
 
具体实现方式需要从左上角到右下角找图片中有星号的区域，找到一个星号就对这个它广度优先搜索，找到所有连续的星号区域，并把这个区域所有星号删除（防止重复搜索），计算星号区域面积，用max存储区域最大值
 
算法复杂度为o(w*h)
 
#include 
#include 
int main(int argc, char *argv[]){
	int farm[80][1000],w,h,i,j,space=0,pos[80000][2],endl,endmove,max=0,x;
	char c[1000];
	scanf("%d%d",&w,&h);
	i=0;
	while(i0&&farm[pos[x][0]-1][farm[x][1]]==1)
						{
							farm[pos[x][0]-1][pos[x][1]]=0;
							pos[endmove][0]=pos[x][0]-1;
							pos[endmove][1]=pos[x][1];
							endmove++;
						}
						if(pos[x][0]0&&farm[pos[x][0]][pos[x][1]-1]==1)
						{
							farm[pos[x][0]][pos[x][1]-1]=0;
							pos[endmove][0]=pos[x][0];
							pos[endmove][1]=pos[x][1]-1;
							endmove++;
						}
						if(pos[x][1] 
原题链接1192 - Prime Path - acm.bjtu
 
输入t组数据，每组为两个四位质数，每步替换第一个质数的某一位数字将它变为第二个质数，要求替换过程中每一步替换完成后得到的数都是质数，输出最短替换步数，如果无法完成则输出Impossible
 
隐性走迷宫题，每一步不再是向四个方向移动，而是将某一位数字变为任意其它数字，而质数相当于迷宫的空地，非质数相当于迷宫的墙
 
先打出1000-9999的质数表，存储在四维数组中（每一维存储其中一位数字，第一位不能存储0，最后一位可以省去存储2、4、6、8、0）
 
数组中搜索过的数字没
 
有替换为和非质数一样的0而是替换为2为了方便测完一组数据后恢复质数表
 
#include 
#include 
int primecheck(int n){
	int i=0,prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
	while(i<25)
	{
		if(n%prime[i]==0)return 0;
		i++;
	}
	return 1;
} 
int main(int argc, char *argv[]) {
	int n,i=1001,pm[9][10][10][5],list[4500][4],st,de,endl,j,x,dest[4],gold,flag,endmove;
	while(i<10000)
	{
		pm[i/1000-1][(i/100)%10][(i/10)%10][(i%10-1)/2]=primecheck(i);
		i+=2;
	}
	i=0;
	scanf("%d",&n);
	while(i