Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我是直接暴力DFS搜索AC的,大牛你这代码没看懂,谁能简单解释一下不,想知道这题如何构图

Posted by hujk2008 at 2012-09-18 14:50:42 on Problem 1103 and last updated at 2012-09-18 14:54:57
In Reply To:问题找到了,w>h和w<=h的情况构图时要分开讨论。。附AC代码 Posted by:yzhw at 2009-04-03 14:07:41
本来我也是想构图的,愣是没啥好方法,只好直接DFS。

Problem: 1103  User: hujk2008 
Memory: 168K  Time: 0MS 
Language: C++  Result: Accepted 


#include <stdio.h>

#define MAXLEN 80

#define _MIN_(a,b) ((a)<=(b)?(a):(b))
typedef struct st_vpath
{
	int dx[3],dy[3] ;
	char expect[3] ;
	int dir[3] ;
	int f  ;
	void set( int i, int x, int y, char c, int d)
	{
		dx[i] = x ;
		dy[i] = y ;
		expect[i] = c ;
		dir[i] = d ;
	};

}vpath;

class CMaze
{
public:
	CMaze() {Init() ;}
	void		Init() ;
	int			Input() ;
	void		Reset() ;
	int			DFS( int x, int y) ;
	void		Solve() ;
	void		Print() ;
	inline char		GetSign(int x1, int y1,int x2,int y2) ;
public:
	int			m_nRow,m_nCol ;
	char		m_map[MAXLEN][MAXLEN] ;
	int			m_nCycleCount ;
	int			m_nMaxLength ;
	vpath		m_path[4] ;
};

void CMaze::Init() 
{
	m_path[0].set(0,1,1,'\\',1) ;
	m_path[0].set(1,1,-1,'/',0) ;
	m_path[0].set(2,-1,-1,'\\',3) ;

	m_path[1].set(0,-1,1,'/',2) ;
	m_path[1].set(1,1,1,'\\',1);
	m_path[1].set(2,1,-1,'/',0) ;

	m_path[2].set(0,-1,-1,'\\',3) ;
	m_path[2].set(1,-1,1,'/',2) ;
	m_path[2].set(2,1,1,'\\',1) ;

	m_path[3].set(0,1,-1,'/',0) ;
	m_path[3].set(1,-1,-1,'\\',3) ;
	m_path[3].set(2,-1,1,'/',2) ;
}
int CMaze::Input() 
{
	int i ;
	scanf("%d%d",&m_nCol,&m_nRow) ;
	if( m_nRow <= 0)
		return 0 ;
	for( i = 0 ;i < m_nRow; i ++)
		scanf("%s",m_map[i]) ;
	return 1 ;
}
void CMaze::Reset() 
{
	m_nCycleCount = m_nMaxLength = 0 ;
	m_path[0].f = m_nRow ;
	m_path[1].f = m_nCol ;
	m_path[2].f = 0 ;
	m_path[3].f = 0 ;
}

char CMaze::GetSign(int x1, int y1,int x2,int y2) 
{
	x1 = _MIN_(x1,x2) ;
	y1 = _MIN_(y1,y2) ;
	return m_map[x1][y1] ;
}
int CMaze::DFS( int x, int y)
{
	int tx = x+1, ty = y -1,i,k ;
	int nx, ny ,nCount = 2;
	
	
	k = 0 ;
	// 从左边深度优先搜索
	do 
	{
		for( i = 0;i < 3 ;i ++ )
		{
			nx = tx + m_path[k].dx[i] ;
			ny = ty + m_path[k].dy[i] ;
			if( nx < 0 || nx > m_nRow ||
				ny < 0 || ny > m_nCol )
				continue ;
			if( GetSign(tx,ty,nx,ny) == m_path[k].expect[i])
			{
				if( i == 2 )
				{
					if( k&1 )
					{
						if( m_path[k].f == ty)
							continue ;
					}else
					{
						if( m_path[k].f == tx)
							continue ;
					}
				}
				
				k = m_path[k].dir[i] ;
				nCount += ( i + 1) ;
				tx = nx , ty = ny ;
				break ;
			}
		}
		
		if ( i == 3)
		{
			// 判断是否可以掉头
			if( tx > 0 && tx < m_nRow &&
				ty > 0 && ty < m_nCol)
			{
				nCount += 4 ;
				tx -= m_path[k].dx[1] ;
				ty -= m_path[k].dy[1] ;
				if(k&1)
					k = 4 - k ;
				else
					k = 2 - k ;
			}else
				return -1 ;
		}
		if( nx < x) // 已经计算过了
			return -1 ;
		if( nx == x && ny < y) // 已经计算过了
			return -1 ;
	
		if(tx == x && ty == y )
		{
			if( k == 3)
				return nCount -1 ;
			return -1 ;
		}
	} while (1);

	return -1 ;

}
void CMaze::Solve() 
{
	int i , j , t;
	Reset() ;
	for( i = 0 ;i < m_nRow - 1; i ++ )
	{
		for( j = 1 ; j < m_nCol ; j ++ )
		{
			if( m_map[i][j-1] == '/' && m_map[i][j] == '\\')
			{
				t = DFS(i,j) ;
				if( t > 0 )
				{
					m_nCycleCount ++ ;
					if( m_nMaxLength < t)
						m_nMaxLength = t ;
				}
			}
		}
	}

}
void CMaze::Print() 
{
	if( m_nCycleCount == 0)
		printf("There are no cycles.\n");
	else
		printf("%d Cycles; the longest has length %d.\n",m_nCycleCount,m_nMaxLength);
}

int main()
{
	CMaze s ;
	int nMazeCount = 1 ;
	while(s.Input())
	{
		s.Solve() ;

		printf("Maze #%d:\n",nMazeCount++) ;
		s.Print() ;
		printf("\n") ;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator