wa.txt

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

#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;
	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;
}

bool Read()
{
	wall = 0;
	success = false;
	if (cin>>N>>M>>T || (N == 0 && M == 0 && T == 0))
		return 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++;
		}
	return true;
}

int main()
{
	while(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;
}