迷宫

题目描述

有一个仅由数字 0 与 1 组成的n*n 格迷宫。若你位于一格 0 上，那么你可以移 动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相 邻 4 格中的某一格 0 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自 身）。

输入格式

第 1 行为两个正整数n,m。 下面 n行，每行n个字符，字符只可能是 0 或者 1 ，字符之间没有空格。 接下来m行，每行 2 个用空格分隔的正整数i,j对应了迷宫中第 i 行第 j列的一个 格子，询问从这一格开始能移动到多少格。

输出格式

m行，对于每个询问输出相应答案。

样例

输入样例

2 2

0 1

1 0

1 1

2 2

输出样例

4

4

#include <bits/stdc++.h>
using namespace std;
struct aaa
{
	int x,y,v;
	aaa()
	{
		x = 0;
		y = 0;
	}
	aaa(int a,int b,int c)
	{
		x = a;
		y = b;
		v = c;
	}
};
aaa que[10010];
int a[110][110];
bool b[110][110];
int n,m;
int cnt;
int head;
int hi;
int tail;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void bfs(int,int);

int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int iii = 1;iii<=m;iii++)
	{
		int ii,jj;
		cin>>ii>>jj;
		bfs(ii,jj);
		cout<<cnt<<endl;
		cnt = 0;
		for(int i = 0;i<=100;i++)
		{
			for(int j = 0;j<=100;j++)
			{
				b[i][j] = 0;
			}
		}
	}
	
	
	return 0;
}
void bfs(int xx,int yy)
{
	head = 0;
	tail = 0;
	que[++tail] = {xx,yy,a[xx][yy]};
	while(head<tail)
	{
		head++;
		for(int i = 0;i<4;i++)
		{
			int tx = que[head].x+dx[i];
			int ty = que[head].y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]!=que[head].v&&b[tx][ty]==0)
			{
				cnt++;
				que[++tail] = {tx,ty,a[tx][ty]};
				b[tx][ty] = 1;
			}
		}
	}
}

鸡飞狗不跳

题目描述

有一只鸡和一条狗，他们在一条线上，鸡的位置在点N处，狗在点M处，鸡和狗约定，狗站那不动，鸡去找狗。可以一次向左或向右走一步，也可一次飞到原来所在位置的2倍处。鸡飞一次和走一步时间相同。为了不让狗等得着急，鸡最快多长时间能到狗的位置。

输入格式

输入一行N,M（0<=N,M<=100000)。

输出格式

输出鸡到狗位置的最短时间。

样例

样例输入1
5 17

样例输出1
4

#include <bits/stdc++.h>
using namespace std;
struct point
{
	int x,v;
	point(){};
	point(int a,int b)
	{
		x = a;
		v = b;
	}
};
point que[100010];
int head = 0;
int tail = 0;
int b[100010];
int n,m;
int cnt;
int dx[] = {1,-1,2};
int main()
{
	cin>>n>>m;
	b[n] = 1;
	que[++tail] = {n,0};
	
	
	while(head<tail)
	{
		head++;
		bool t = false;
		for(int i = 0;i<3;i++)
		{
			int tx;
			if(i==2)
			{
				tx = que[head].x*dx[i];
			}
			else
			{
				tx = que[head].x+dx[i];
			}
			if(tx>=1&&tx<=100010&&b[tx]==0)
			{
				b[tx] = 1;
				que[++tail] = {tx,que[head].v+1};
				if(tx==m)
				{
					t = true;
					break;
				}
			}
		}
		if(t==true)
		{
			break;
		}
		
	}
	
	cout<<que[tail].v;
	
	return 0;
}