maze_dfsdlg.cpp

solve maze with dfs and bfs

// maze_dfsDlg.cpp : implementation file
//

#include "stdafx.h"
#include "maze_dfs.h"
#include "maze_dfsDlg.h"
#include <queue>
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif


/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMaze_dfsDlg dialog

CMaze_dfsDlg::CMaze_dfsDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMaze_dfsDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CMaze_dfsDlg)
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CMaze_dfsDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMaze_dfsDlg)
	DDX_Control(pDX, IDC_EDIT5, m_finish_y);
	DDX_Control(pDX, IDC_EDIT2, m_finish_x);
	DDX_Control(pDX, IDC_EDIT4, m_start_y);
	DDX_Control(pDX, IDC_EDIT1, m_start_x);
	DDX_Control(pDX, IDC_EDIT3, m_total);
	DDX_Control(pDX, IDC_MSFLEXGRID1, m_fg1);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMaze_dfsDlg, CDialog)
	//{{AFX_MSG_MAP(CMaze_dfsDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

using namespace std;
struct Node
{
	int Row, Col, Step;
	Node(int r=0, int c=0, int s=0)
	{
		Row=r;
		Col=c;
		Step=s;
	}
};

class CMaze
{
public:
	int board[12][12];
	int Cell[12][12];
//	char Cell[12][12];
	int x[4],y[4],count;
	CMSFlexGrid *_fg;
	CMaze(int _x=0, int _y=0)
	{
		int i,j;
		x[0]=0; y[0]=1;
		x[1]=0; y[1]=-1;
		x[2]=-1; y[2]=0;
		x[3]=1; y[3]=0;
		

		for(i=0;i<12;i++)
		{
			for(j=0;j<12;j++)
			{
				if(((j==1||j==2||j==3||j==4||j==11)&&i==0)||((j==4||j==6||j==7||j==11)&&i==1)||((j==0||j==1||j==2||j==4||j==6||j==11)&&i==2))
					board[i][j]=3;
				else if(((j==0||j==4||j==6||j==8||j==9||j==10||j==11)&&i==3)||((j==0||j==2||j==3||j==4||j==6)&&i==4)||((j==0||j==6||j==8||j==9)&&i==5))
					board[i][j]=3;
				else if(((j==0||j==1||j==2||j==4||j==5||j==6||j==7||j==8||j==9||j==11)&&i==6)||((j==2||j==4||j==11)&&i==7)||((j==2||j==4||j==6||j==7||j==8||j==11)&&i==8))
					board[i][j]=3;
				else if(((j==1||j==2||j==4||j==8||j==11)&&i==9)||((j==4||j==5||j==6||j==8||j==11)&&i==10)||((j==8||j==9||j==10||j==11)&&i==11))
					board[i][j]=3;
				else
					board[i][j]=0;
			}
		}
		
	}
	void set_start(int _x, int _y)
	{
		if(board[_x][_y]==0)
		{
			board[_x][_y]=1;
		}
	}
	void set_finish(int tuj_x, int tuj_y)
	{
		if(board[tuj_x][tuj_y]==0)
		{
			board[tuj_x][tuj_y]=5;
		}
	}
	bool solve(int posx, int posy)
	{
		int i;
		if(board[posy][posx]==5)
		{
			return 1;
		}
		else
		{
			for(i=0;i<4;i++)
			{
				posx=posx+x[i];
				posy=posy+y[i];
				if((posx>=0)&&(posx<12)&&(posy>=0)&&(posy<12)) //pengecekan valid
				{
					
					if(board[posy][posx]==5)
					{
						return 1;
					}
					else if(board[posy][posx]==0) //pengecekan isi
					{
						count=count+1;
						board[posy][posx]=1;
						print();
						if(solve(posx,posy))
							return 1;
						board[posy][posx]=0;
					}
					
				}
				posx=posx-x[i];
				posy=posy-y[i];
			}
		}
		return 0;
	}
	void print()
	{
		int i,j;
		CString str;
		for(i=0;i<12;i++)
		{
			for(j=0;j<12;j++)
			{
				str.Format("%d",board[i][j]);
				_fg->SetRow(i);
				_fg->SetCol(j);
				_fg->SetText(str);
				//_fg.SetTextMatrix(i,j,str);
			}
		}

	}
	void print1()
	{
		int i,j;
		CString str;
		for(i=0;i<12;i++)
		{
			for(j=0;j<12;j++)
			{
				str.Format("%d",Cell[i][j]);
				_fg->SetRow(i);
				_fg->SetCol(j);
				_fg->SetText(str);
				//_fg.SetTextMatrix(i,j,str);
			}
		}

	}
	
int CountMaze(int KRow, int KCol, int DestRow, int DestCol)
{
//	int count=1;
	//jika sudah sampai pada langkah pertama
	if(KRow==DestRow && KCol==DestCol)
		return 0;
	queue<Node> q;

	//board
	for(int i=0;i<12;i++)	//init board
	{
		for(int j=0;j<12;j++)
		{
			if(((j==1||j==2||j==3||j==4||j==11)&&i==0)||((j==4||j==6||j==7||j==11)&&i==1)||((j==0||j==1||j==2||j==4||j==6||j==11)&&i==2))
				Cell[i][j]=3;
			else if(((j==0||j==4||j==6||j==8||j==9||j==10||j==11)&&i==3)||((j==0||j==2||j==3||j==4||j==6)&&i==4)||((j==0||j==6||j==8||j==9)&&i==5))
				Cell[i][j]=3;
			else if(((j==0||j==1||j==2||j==4||j==5||j==6||j==7||j==8||j==9||j==11)&&i==6)||((j==2||j==4||j==11)&&i==7)||((j==2||j==4||j==6||j==7||j==8||j==11)&&i==8))
				Cell[i][j]=3;
			else if(((j==1||j==2||j==4||j==8||j==11)&&i==9)||((j==4||j==5||j==6||j==8||j==11)&&i==10)||((j==8||j==9||j==10||j==11)&&i==11))
				Cell[i][j]=3;
			else
				Cell[i][j]=0;
		}
	}

	int dr[4], dc[4];		//step
	dr[0]=0; dc[0]=1;		//kanan atas 1
	dr[1]=-1; dc[1]=0;		//kanan atas 2
	dr[2]=1;  dc[2]=0;
	dr[3]=0;  dc[3]=-1;
	

	Node Root(KRow, KCol);	//init knight
	q.push(Root);			//simpan
	Cell[KRow][KCol]=1;	//tandai
//	count=count+1;
	while(!q.empty())
	{
		//ambil palig depan
		Node Current=q.front();
		q.pop();
		//untuk tiap kemungkinan langkah
		for (i=0;i<4;i++)
		{
			//cek valid board
			
			if(Current.Row+dr[i]>=0 && Current.Row+dr[i]<12 && Current.Col+dc[i]>=0 && Current.Col+dc[i]<12)
			{
				//cek sudah dijalani
				if(Cell[Current.Row+dr[i]][Current.Col+dc[i]]==0)
				{
					//buat node baru
					
					Cell[Current.Row+dr[i]][Current.Col+dc[i]]=1;
					//print1();
					Node Child(Current.Row+dr[i],Current.Col+dc[i],Current.Step+1);
					//Jika node baru adalah kotak tujuan -->keluar, kembalikan jarak sekarang
					if(Child.Row==DestRow && Child.Col==DestCol) return Child.Step;
					else 
						q.push(Child);
				}
			}
		}
		count=count+1;
	}

	return -1;
}
};
CMaze maze(0,0);


/////////////////////////////////////////////////////////////////////////////
// CMaze_dfsDlg message handlers

BOOL CMaze_dfsDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	CString str4;
	for(int i=0; i<12;i++)
		{
			for(int j=0;j<12;j++)
			{			
				str4.Format("%d",maze.board[i][j]);
				m_fg1.SetTextMatrix(i,j,str4);
			}
		}
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CMaze_dfsDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMaze_dfsDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMaze_dfsDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}




void CMaze_dfsDlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	CString str,str1,str2,str3,str4;
	m_start_x.GetWindowText(str1);
	m_start_y.GetWindowText(str);
	m_finish_x.GetWindowText(str3);
	m_finish_y.GetWindowText(str2);
	maze.set_start(atoi(str),atoi(str1));
	maze.set_finish(atoi(str2),atoi(str3));
	for(int i=0; i<12;i++)
	{
		for(int j=0;j<12;j++)
		{			
			str4.Format("%d",maze.board[i][j]);
			m_fg1.SetTextMatrix(i,j,str4);
		}
	}
}

void CMaze_dfsDlg::OnButton2() 
{
	// TODO: Add your control notification handler code here
	CString str,str1,str4;
	m_start_x.GetWindowText(str1);
	m_start_y.GetWindowText(str);
	maze._fg = (CMSFlexGrid *) GetDlgItem(IDC_MSFLEXGRID1);
	if(maze.solve(atoi(str1),atoi(str)))
	{
		for(int i=0; i<12;i++)
		{
			for(int j=0;j<12;j++)
			{			
				str4.Format("%d",maze.board[i][j]);
				m_fg1.SetTextMatrix(i,j,str4);
			}
		}
		str4.Format("%d",maze.count);
		m_total.SetWindowText(str4);
	}
	else 
	{
		AfxMessageBox("Cannot be solved!!");
	}
}

void CMaze_dfsDlg::OnButton3() 
{
	// TODO: Add your control notification handler code here
	CString str,str1,str2,str3,str4;
	
	m_start_x.GetWindowText(str1);
	m_start_y.GetWindowText(str);
	m_finish_x.GetWindowText(str3);
	m_finish_y.GetWindowText(str2);
	int langkah=maze.CountMaze(atoi(str),atoi(str1),atoi(str2),atoi(str3));
	maze._fg = (CMSFlexGrid *) GetDlgItem(IDC_MSFLEXGRID1);
	if(langkah==-1)
	{
		AfxMessageBox("Cannot be solved!!");
	}
	else 
	{
		for(int i=0; i<12;i++)
		{
			for(int j=0;j<12;j++)
			{			
				str4.Format("%d",maze.Cell[i][j]);
				m_fg1.SetTextMatrix(i,j,str4);
			}
		}
		str4.Format("%d",langkah);
		m_total.SetWindowText(str4);
	}
}

void CMaze_dfsDlg::OnButton4() 
{
	// TODO: Add your control notification handler code here
	CString str,str1,str2,str3,str4;
	m_start_x.GetWindowText(str1);
	m_start_y.GetWindowText(str);
	m_finish_x.GetWindowText(str3);
	m_finish_y.GetWindowText(str2);
	maze.set_start(atoi(str),atoi(str1));
	maze.set_finish(atoi(str2),atoi(str3));
	for(int i=0; i<12;i++)
	{
		for(int j=0;j<12;j++)
		{
			str4.Format("%d",maze.board[i][j]);
			m_fg1.SetTextMatrix(i,j,str4);
		}
	}
}