1983.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1983
#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 8;
int n,m,tle;
char mat[MAX][MAX+1];
bool hash[MAX][MAX][2];
struct NODE {
	int x,y;
	bool dmd;
	bool isok() {
		if (x<0||x>=n||y<0||y>=m||mat[x][y]=='#') return false;
		if (mat[x][y] == 'J') dmd = 1;
		if (hash[x][y][dmd]) return false;
		hash[x][y][dmd] = true;
		return true;
	}
	bool isend() {
		return (dmd && mat[x][y]=='E');
	}
}ns;
queue<NODE> sq;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool check() {
	NODE now,next;
	int i,j,t = 0;
	while (!sq.empty()) sq.pop();
	sq.push(ns);
	memset(hash,false,sizeof(hash));
	ns.isok();
	while (!sq.empty()) {
		int l = sq.size();
		t ++;
		if (t > tle) return false;
		while (l --) {
			now = sq.front();
			sq.pop();
			for (i=0;i<4;i++) {
				next = now;
				next.x += dir[i][0];
				next.y += dir[i][1];
				if (next.isok()) {
					if (next.isend()) return true;
					sq.push(next);
				}
			}
		}
	}
	return false;
}
bool dfs(int block,int i,int j) {
	if (block == 0) return !check();
	for (;i<n;i++,j=0) for (;j<m;j++) {
		if (mat[i][j]=='#' || mat[i][j]=='S' || mat[i][j]=='E') continue;
		char chtmp = mat[i][j];
		mat[i][j] = '#';
		if (dfs(block-1,i,j+1)) return true;
		mat[i][j] = chtmp;
	}
	return false;
}
int main() {
	int i,j,cas;
	scanf("%d",&cas);
	while (cas --) {
		scanf("%d %d %d",&n,&m,&tle); getchar();
		tle = min(tle,64);
		for (i=0;i<n;i++) {
			gets(mat[i]);
			for (j=0;j<m;j++) {
				if (mat[i][j] == 'S') {
					ns.x = i;
					ns.y = j;
					ns.dmd = 0;
				}
			}
		}
		for (i=0;i<4;i++) {
			if (dfs(i,0,0)) break;
		}
		printf("%d\n",i);
	} 
}