8th_D

                         D. 穿越机房
问题描述
   众所周知,在机房里想从一个地方到另一个地方很困难。因为机房里不仅有很多的
桌子,还摆了很多的椅子。现在,建冬哥想找嘉娃一起 apom,他不能在众目睽睽之下
对着嘉娃大吼,所以,他必须走到嘉娃跟前。
   我们把机房分为宽度为 w,高度为 h 的 w × h 个格子。每个格子或者是一张桌子,
或者有一把椅子,或者什么都没有。建冬哥不能通过有桌子的格子,可以以一个单位时
间通过什么都没有的格子,但是通过有椅子的格子时,建冬哥需要花两个单位时间。
   现在给出建冬哥和嘉娃的位置,以及机房的构造,你能知道建冬哥最快要多长时间
才能到嘉娃身边吗?
输入格式
   第一行 6 个整数 w, h, sr, sc, er, ec(3 ≤ w, h ≤ 20)。 w 和 h 表示机房的大小, (sr, sc)
表示建冬哥处在第 sr 行第 sc 列,同理 (er, ec) 表示目前嘉娃的位置。开始时建冬哥和
嘉娃肯定在机房里。接下来是一个 w × h 的矩阵,代表机房的地形:
   • '.': 表示该格子没有障碍物,通过需要 1 个单位时间。
   • '*': 表示该格子有一把椅子,通过需要 2 个单位时间。
   • 'x': 表示该格子是一张桌子,不能通过。
输出格式
   一个整数,表示建冬哥到嘉娃所在位置的最短时间。之后加一个换行。
样例输入
4 6 1 1 4 6
******
......
*xx*x.
.*...*
样例输出
11
提示
   最后的输出结果为建冬哥经过路径上所有点的时间之和。

#include<cstdio>

int a[22][22];
int w=0,h=0,sr=0,sc=0,er=0,ec=0;
int min=100000;

void prework(){
	scanf("%d %d %d %d %d %d",&w,&h,&sr,&sc,&er,&ec);
	for(int j=1;j<=h;j++){
		a[0][j]=-1;
		a[w+1][j]=-1;
	}
	for(int i=1;i<=w;i++){
		a[i][0]=-1;
		a[i][h+1]=-1;
	}
	char s[20];
	for(int i=1;i<=w;i++){
		scanf("%s",s);
		for(int j=1;j<=h;j++){
			if(s[j-1]=='.')
				a[i][j]=1;
			else if(s[j-1]=='*')
				a[i][j]=2;
			else if(s[j-1]=='X')
				a[i][j]=-1;
		}
	}
}
void search(){
	if((sr==er)&&(sc==ec)){
		min = a[sr][sc];
		return;
	}
	int del_r[4]={1,-1,0,0};
	int del_c[4]={0,0,1,-1};
	struct unit{
		int r;
		int c;
		int time;
	};
	unit queue[4000];
	int p=0,q=1;


	queue[0].r = sr;
	queue[0].c = sc;
	queue[0].time=a[sr][sc];
//	printf("%d: %d %d %d\n",p,queue[p].r,queue[p].c,queue[p].time);
	while(p!=q){
		for(int i=0;i<4;i++){
			int r = queue[p].r+del_r[i];
			int c = queue[p].c+del_c[i];
			if(1==a[r][c]){
				bool flag = true;
				for(int j=0;j<q;j++){
					if((queue[j].r==r)&&(queue[j].c==c)&&(queue[j].time<=queue[p].time+1)){
						flag = false;
						break;
					}
				}
				if(!flag) continue;
				queue[q].r=r;
				queue[q].c=c;
				queue[q].time = queue[p].time+1;

//				printf("%d: %d %d %d\n",q,queue[q].r,queue[q].c,queue[q].time);
				if((queue[q].r==er)&&(queue[q].c==ec)&&(min>queue[q].time)){
					min = queue[q].time;
				}
				q++;
			}
		}
		for(int i=0;i<4;i++){
			int r = queue[p].r+del_r[i];
			int c = queue[p].c+del_c[i];
			if(2==a[r][c]){
				bool flag = true;
				for(int j=0;j<q;j++){
					if((queue[j].r==r)&&(queue[j].c==c)&&(queue[j].time<=queue[p].time+2)){
						flag = false;
						break;
					}
				}
				if(!flag) continue;
				queue[q].r=r;
				queue[q].c=c;
				queue[q].time = queue[p].time+2;

//				printf("%d: %d %d %d\n",q,queue[q].r,queue[q].c,queue[q].time);
				if((queue[q].r==er)&&(queue[q].c==ec)&&(min>queue[q].time)){
					min = queue[q].time;
				}
				q++;
			}
		}
		p++;
	}
}
int main(){
	prework();
//	for(int i=0;i<=w+1;i++){
//		for(int j=0;j<=h+1;j++){
//			printf("%d ",a[i][j]);
//		}
//		printf("\n");
//	}
	search();
	printf("%d\n",min);
	return 0;
}