队列

队列的定义

队列是一种运算受限的线性表，仅允许在表的一端进行插入，而在表的另一端进行删除。通常把进行插入的一端称为队尾，进行删除的一端称为队首，队列不允许在中间部位进行操作！

队列的性质：先进先出

队列的存储结构

顺序存储和链式存储

顺序队列的基本操作

#define N 100       //队列长度
struct queue{
	int que[N]  //队列
	int head;   //队首指针
	int tail;   //队尾指针
}que;
head=tail=0;        //初始化队列
que[tail++]=x;      //元素入队
head++;             //队首元素出队
head>=tail;         //队列为空的判断

链表队列的基本操作

//为了方便，队列元素设为 int 
//创建队列节点元素 
typedef struct qnode{
	int data;
	struct qnode *next;
}QNode;
//创建队列的首尾指针 
typedef struct{
	QNode *head;
	QNode *tail;
}Queue;

QNode *p;               //插入或删除的节点 

Queue->head==NULL      //队列为空 
//或Queue->tail==NULL
 
Queue->tail->next=p;  //元素p入队 
Queue->tail=p;

p=Queue->head;        //队首元素出列 
Queue->head=p->next;
int x=p->data;            //队首元素的值 
free(p);

解决队列问题要点

1. 队列不为空的条件判断
2. 入队出队条件

队列习题

实例1：

寻路（广度优先搜索）

#include<stdio.h>
struct note{
	int x;//横坐标 
	int y;//纵坐标 
	int f;//父节点 
	int s;//步数 
}; 
int main()
{
	struct note que[2500];//队列 
	
	int a[50][50]={0},book[50][50]={0};
	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//表示四个方向 
	int head,tail;
	int i,j,k,n,m,startx,starty,endx,endy,tx,ty,flag;
	scanf("%d %d",&n,&m);//横列数 
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		scanf("%d",&a[i][j]);
	scanf("%d %d %d %d",&startx,&starty,&endx,&endy);//起始结束坐标
	//队列初始化 
	head=tail=0;
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].s=0;
	que[tail].f=0;
	tail++;
	//标记走过的点 
	book[startx][starty]=1;
	//标记是否走到终点 
	flag=0;
	//队列不为空时 
	while(head<tail)
	{
		for(k=0;k<4;k++)
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			if(tx<0||tx>n-1||ty<0||ty>m-1)
				continue;
			if(a[tx][ty]==0&&book[tx][ty]==0)
			{
				book[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].s=que[head].s+1;
				que[tail].f=head;
				tail++;
			}
			if(tx==endx&&ty==endy)
			{
				flag=1;
				break;
			}
		}
		if(flag==1)
			break;
		head++;
	}
	printf("%d",que[tail-1].s);
	return 0;
}

测试用例：

输入：

5 4

0 0 1 0

0 0 0 0

0 0 1 0

0 1 0 0

0 0 0 1

0 0 3 2

输出 ：

7

实例2：

Problem Description

根据亚马逊棋估值方法判断当前局面下白方的估值得分。

queen move：8个方向一次移动任意格，不能跨越障碍
King move：8个方向一次移动一格，不能跨越障碍

Input

输入数据可能不止一组，每组测试样例间有一个空行，每组输入数据均有10行，每行10个字符，其中".”代表空棋格（没有棋子或障碍），"X”代表障碍，"W”代表白子，"R”代表黑子。

Output

输出白方局面评估的值，每个局面的估值包括：按照queen move标记，白方步数少于黑方步数的格子数与白方步数多于黑方步数格子数之差。

                                                           按照king move标记，白方步数少于黑方步数的格子数与白方步数多于黑方步数格子数之差。

每组输入数据所对应的输出结果占一行。

 

例

输入：

..XRX.....

..WXX.....

..XXRXXXX.

.XX.X.W.X.

X....X....

.XX..XXX..

...W...X..

.X.....W.X

...R..R...

X......X..

对应棋局为：

示例左图：每小格左上角数字表示任意白棋queen move到此位置的最少步数
  每小格右下角数字表示任意黑棋queen move到此位置的最少步数
示例右图：每小格左上角数字表示任意白棋King move到此位置的最少步数
  每小格右下角数字表示任意黑棋King move到此位置的最少步数
图中黑色格子表示障碍

输入

.RRX.XXX.XX....XX.R...X..X.WXXX........WXX.X.....X.X.RXX.WX..X....X..XX.WXX.X..XXX.....X..XX..X.X.X.RX.XXXXXX.XX.X.X...XXWXXWXRXX.XXXXX.XXX.XX.X.XXXX..XXX..XXXXXXXXWXXRX.XWXXX.XXXXX.XXXX.XX.XXXRXX.X.X

输出

case 1: queen win:-3 king win:4

case 2: queen win:2 king win:2

题意：分别输出QueebMove和KingMove标记的估值（注：Queen走法是指移动的八个方向上只要没有跨越障碍(障碍包括棋子和箭)就可以移动；而King走法是指一次移动距离是1，也就是只能走步到相邻的空格）。

题解：因为是分别输出QueenMove和KingMove,故要分别进行两次BFS搜索。搜索起点从棋子开始，遇到边界、其他棋子和陷阱停止。刚开始写的是从空格开始搜到棋子等结束，但是QueenMove不好办，KingMove会超时。KingMove具体比较好操作，就是一个纯粹的BFS，没有什么特殊的地方；QueenMove需要注意一下，它一次可移动的八个方向步数均为1，在这里用"while(1)"操作，对着一个方向搜到底，遇到边界条件再弹出，但是这个会遇到有种情况，就是后来的会与之前搜过的产生冲突，即vis[][]已经被标记为1，不能再走，这样就会阻止对一个方向搜到底，对于这个情况，我们选择"continue"即之前搜过的我们就跳过就好了，也许还不明白这种情况具体是怎样，下面给出图示参考，黑色表示之前的一次搜索，红色表示之后的一次搜索，黄色表示产生冲突。

#include<stdio.h>
#define N 10
struct node1{
	int kw,kr,qw,qr;
}map[N][N];
struct node2{
	int x;
	int y;
	int step;
}que[110];
char Map[N][N+1];
int TmpChess1[N][N],TmpChess2[N][N];
int next[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int head,tail;
void King(int x,int y)
{
	int tx,ty;
	head=tail=0;
	que[tail].x=x;  que[tail].y=y;	que[tail].step=0;  //队列初始化 
	tail++;
	while(head<tail){
		for(int k=0;k<8;k++)
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			if(tx<0||tx>N-1||ty<0||ty>N-1||TmpChess1[tx][ty]!=0)
				continue;
			else{
				TmpChess1[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].step=que[head].step+1;
				tail++;
			}
		}
		head++;
	}
	for(int k=1;k<tail;k++){
	if(Map[x][y]=='W' && map[que[k].x][que[k].y].kw>que[k].step)
		map[que[k].x][que[k].y].kw=que[k].step;
	if(Map[x][y]=='R' && map[que[k].x][que[k].y].kr>que[k].step)
		map[que[k].x][que[k].y].kr=que[k].step;
	}
}
void Queen(int x,int y)
{
	int tx,ty;
	head=tail=0;
	que[tail].x=x;  que[tail].y=y;  que[tail].step=0;
	tail++;
	TmpChess2[x][y]=1;
	while(head<tail)
	{
		for(int k=0;k<8;k++)
		{
			tx=que[head].x;
			ty=que[head].y;
			while(1){
				tx=tx+next[k][0];
				ty=ty+next[k][1];
				if(tx>=0&&tx<N&&ty>=0&&ty<N&&TmpChess2[tx][ty]==-1) continue;
				if(tx>=0&&tx<N&&ty>=0&&ty<N&&TmpChess2[tx][ty]==0) {
					TmpChess2[tx][ty]=-1;
					que[tail].x=tx;
					que[tail].y=ty;
					que[tail].step=que[head].step+1;
					tail++;
				}
				else 
				break;
			}
		}
		head++;
	}
	for(int k=1;k<tail;k++){
	if(Map[x][y]=='W' && map[que[k].x][que[k].y].qw>que[k].step)
		map[que[k].x][que[k].y].qw=que[k].step;
	if(Map[x][y]=='R'&& map[que[k].x][que[k].y].qr>que[k].step)
		map[que[k].x][que[k].y].qr=que[k].step;
	}
}
int main()
{
	int n=1,i,j,queen,king;
	while (scanf("%s",Map[0])!=EOF)
	{
		queen=0,king=0;
		for (i = 1; i < N; i++)
			scanf("%s",Map[i]);
		for(i=0;i<N;i++)
			for(j=0;j<N;j++){
				map[i][j].kr=10000;	map[i][j].kw=10000;
				map[i][j].qr=10000;	map[i][j].qw=10000;
			}
		for(i=0;i<N;i++)			//遍历每一个点，若是棋子就进行搜索 
			for(j=0;j<N;j++)
				if(Map[i][j]=='W'||Map[i][j]=='R')
				{
					for(int k=0;k<N;k++)	//拷贝棋盘副本 
						for(int t=0;t<N;t++)
							if(Map[k][t]=='.')
								TmpChess1[k][t]=TmpChess2[k][t]=0;
							else
								TmpChess1[k][t]=TmpChess2[k][t]=1;
					Queen(i,j);	
				   	King(i,j);	
				}
		for(i=0;i<N;i++)			
			for(j=0;j<N;j++)
				if(Map[i][j]=='.')
				{
					if(map[i][j].kw<map[i][j].kr) king++;
					if(map[i][j].kw>map[i][j].kr) king--;
					if(map[i][j].qw<map[i][j].qr) queen++;
					if(map[i][j].qw>map[i][j].qr) queen--;
				}
		printf("case %d: queen win:%d king win:%d\n",n++,queen,king);
	}
	return 0;
}