ac.txt

来自「HDUOJ_ACM题目集合~~希望各位能用得上」· 文本 代码 · 共 73 行

// 1010.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
# include <string.h> 
# include <stdlib.h> 
using namespace std;

char map[9][9];
bool success;
int N,M,T;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int si, sj, di,dj;
int wall;

void DFS(int i, int j, int step)
{
	if (i > N || i <= 0 || j > M || j <= 0)
		return;
	if (i == di && j == dj && step == T)
		success = true;
	if (success == true)
		return;
	int temp = (T-step)-abs(i-di)-abs(j-dj);
	if (temp < 0 || temp && 1) return;		//temp & 1而不是temp && 1!!!!!!!!
	for (int temp = 0; temp < 4; temp ++)
	{
		if (map[i+dir[temp][0]][j+dir[temp][1]] != 'X')
		{
			map[i+dir[temp][0]][j+dir[temp][1]] = 'X';
			DFS(i+dir[temp][0], j+dir[temp][1],step+1);
			map[i+dir[temp][0]][j+dir[temp][1]] = '.';
		}
	}
	return;
}

void Read()
{
	wall = 0;
	success = false;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin>>map[i][j];
			if (map[i][j] == 'D') {di = i; dj = j;}
			else if (map[i][j] == 'S') {si = i; sj = j;}
			else if (map[i][j] == 'X') wall++;
		}
}

int main()
{
	while(cin>>N>>M>>T)
	{
		if (N==0 && M==0 && T==0)
			break;
		Read();
		if (wall >= N*M-T)
		{
			cout<<"NO"<<endl;
			continue;
		}
		map[si][sj] = 'X';
		DFS(si,sj,0);
		if (success == true)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}