hdu 4528の検索

4561 ワード

小明シリーズ
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 683 Accepted Submission(s): 182
Problem Description
明ちゃんのお母さんは三人の子供を産んで、ボスは大明、次男は二明、三番目...、三番目は自然に明ちゃんと呼ばれました.
ある日、明ちゃんのお母さんは明ちゃんの兄弟3人を公園に連れて遊びに行きました.公園の中には木がたくさんあって、隠れる場所がたくさんあるので、隠れん坊をすることにしました.数回のじゃんけんの後、第1ラウンドは明ちゃんが他の2人を探しに来たので、ゲームのルールは簡単です.
明ちゃんが規定の時間内に彼らを見つけることができさえすれば、明ちゃんが勝っても、発見された2人のじゃんけんは誰が次のラウンドで責任を持って人を探すかを決めます.もし規定の時間内に一人しか見つからなかったら、発見されなかった人が勝って、発見された人は次のラウンドで人を探す責任を負います.もし規定の時間内に一人も見つからなかったら、明ちゃんは失敗して、次のラウンドはやはり彼が人を探しに来ました.今、明ちゃんは規定の時間内に、自分がすべての人を見つけることができるかどうか知りたいと思っています.今、彼はあなたに計算を手伝ってもらいたいと思っています.
簡単にするために、公園をn行m列の行列と見なし、そのうち「S」は明ちゃんを表し、「D」は大名を表し、「E」は二明を表し、「X」は障害物を表し、「.」は通路を表す.ここで,発見を直接相手を見ることができる,すなわち2人が同じ行または同じ列にあり,その間に障害物がない,あるいは他の人がいないと相手を見ることができると定義する.また、大明、二明蔵ができてから位置を変えることはなく、明ちゃんは単位時間ごとに現在の位置から隣接する4つの位置の1つまで歩くことができ、公園を出ないと仮定します.

Input
テストデータの最初の行は正の整数Tであり、Tグループのテストデータがあることを示す.
各試験データのセットは、まず3つの正の整数n,m,tであり、それぞれ行数、列数、および所定の時間を表し、次にn行、各行m個の上述の文字があり、かつ1つの’S’,1つの’E’,1つの’D’が保証される.
[Technical Specification]
T < 200
3 <= n, m <= 100
0 <= t <= 100

Output
各グループはまず1行Case cを出力する:(cは現在のグループ数を表し、1からカウントする);
次の行では、明ちゃんが所定の時間内にすべての人を見つけることができれば、最低必要な時間を出力します.そうしないと、-1を出力します.

Sample Input


   
   
   
   
    
    
    
    3
5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
......

Sample Output


   
   
   
   
    
    
    
    Case 1:
-1
Case 2:
3
Case 3:
-1

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=100+10;
char Map[MAX][MAX];
bool DR[MAX],DC[MAX],ER[MAX],EC[MAX];//                
int mark[MAX][MAX][2][2];
int n,m,t,dr,dc,er,ec;//  D,E      
int dir[4][2]={0,1,0,-1,1,0,-1,0};

struct Node{
	int x,y,t;
	bool d,e;
	Node(){}
	Node(int X,int Y,int T,bool D,bool E):x(X),y(Y),t(T){d=D,e=E;}
}start;

void Init(int &n,int &m){
	memset(DR,false,sizeof(bool)*(n+1));
	memset(ER,false,sizeof(bool)*(n+1));
	memset(DC,false,sizeof(bool)*(m+1));
	memset(EC,false,sizeof(bool)*(m+1));
}

void Mark(int i,int j,bool *flagR,bool *flagC){
	int x=i,y=j;
	while(++x<n && (Map[x][j] == '.' || Map[x][j] == 'S'))flagR[x]=true;
	while(++y<m && (Map[i][y] == '.' || Map[i][y] == 'S'))flagC[y]=true;
	x=i,y=j;
	while(--x>=0 && (Map[x][j] == '.' || Map[x][j] == 'S'))flagR[x]=true;
	while(--y>=0 && (Map[i][y] == '.' || Map[i][y] == 'S'))flagC[y]=true;
}

void check(bool &d,bool &e,int x,int y){//              
	d=((DR[x] && dc == y) || (DC[y] && dr == x) || d);
	e=((ER[x] && ec == y) || (EC[y] && er == x) || e);
}

int BFS(int &flag){
	check(start.d,start.e,start.x,start.y);
	if(start.d && start.e)return 0;
	queue<Node>q;
	Node oq,next;
	q.push(start);
	mark[start.x][start.y][start.d][start.e]=flag;
	while(!q.empty()){
		oq=q.front();
		q.pop();
		if(oq.t>=t)return -1;
		for(int i=0;i<4;++i){
			next=Node(oq.x+dir[i][0],oq.y+dir[i][1],oq.t+1,oq.d,oq.e);
			if(next.x<0 || next.y<0 || next.x>=n || next.y>=m)continue;
			if(Map[next.x][next.y] != '.' || mark[next.x][next.y][next.d][next.e] == flag)continue;
			mark[next.x][next.y][next.d][next.e]=flag;
			check(next.d,next.e,next.x,next.y);
			if(next.d && next.e)return next.t;
			q.push(next);
		}
	} 
	return -1;
}

int main(){
	int T,num=0;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&t);
		Init(n,m);
		for(int i=0;i<n;++i)scanf("%s",Map[i]);
		for(int i=0;i<n;++i){
			for(int j=0;j<m;++j){
				if(Map[i][j] == 'S')start=Node(i,j,0,0,0);
				else if(Map[i][j] == 'D')dr=i,dc=j,Mark(i,j,DR,DC);
				else if(Map[i][j] == 'E')er=i,ec=j,Mark(i,j,ER,EC);
			}
		}
		int Time=BFS(++num);
		printf("Case %d:
%d
",num,Time);
	}
	return 0;
}

【Java】IOフローの基礎知識

Slurmを改造するために必要だったこと(3)