📄 bfs.bak
字号:
#include"stdio.h"
#include"conio.h"
#include"string.h"
#include"ctype.h"
#include"dos.h"
#include"stdlib.h"
#include"io.h"
#include"dir.h"
#include"math.h"
#include"graphics.h"
#define min 10
#define max 100
#define max1 15
#define sqm(x) (x)*(x)
#define pi 3.14159262
#define bp(x) (x)*(x)
#define Max 100
#define MV_LBUTTON 1
#define MV_RBUTTON 2
#define MV_BBUTTON 3
union REGS reg;
int x,y,button;
typedef struct tagNode
{
int dx;
int dy;
}
NODE;
struct node
{
int data;
struct node *next;
};
struct node *ke[15];
typedef struct chitietdinh
{
float z;
float o;
};
NODE nut[20];
int canh[15][15];
int i,j,sodinh,cohuong;
FILE *f;
int solt;
int truoc[100],chuaxet[max],queue[max];
int t=1,khuyen[10];
char *p;
int cap[30];
char *D[]={"1","2","3","4","5","6","7","8","9","10","11","12","13","14","15"};
int v[]={100,100,25,200,50,300,150,200,200,100,300,150,275,250,175,375,350,325,400,225,400,125,525,125,550,225,450,300,550,350};
int index[100];
int tDFS=200;
int tBFSDQ=200;
int yDFS=20;
int s1;
int vitriDFS[100];
int sodinh1;
int a[100][100];
int X[100];
// int x[100],y[100];
int chuaxet1[100];
int n,kt=1,ch;
int flag=0,v0,spt;
int x1,x2,y1,y2,xm,ym,chuottrai,chuotphai,banphim,dinh1,dinh2,dinh3,dinh4;
unsigned char rm=0,lm=0;
int midx=639/2;
int midy=479/2;
int ke1[Max][Max];
chitietdinh ctd[Max];
int NUMBER_BUTTONS = 2;
int MOUSE_SIZE = 16;
unsigned char MOUSE_THERE;
unsigned char MOUSE_VISIBLE;
unsigned char LBUTTON_DOWN,
RBUTTON_DOWN,
BBUTTON_DOWN,
LBUTTON_UP,
RBUTTON_UP,
BBUTTON_UP,
CURSOR_MOVED;
int CMX = 0,
CMY = 0;
int BSTATE = 0;
union REGS mregs;
struct SREGS msegregs;
unsigned char EGA_REG_READ = 1;
unsigned char lbutton, rbutton;
int xmouse, ymouse;
//////////////khai bao cac ham//////////////////////////////////////////////////
void control_program();
void control_program_start();
void interface();
void help();
void kiemtra(int,int a[][max1]);
void kiemtrafile1(int,int a[][max1]);
void vechuback();
void taofile(int &n,int &h,int a[][max1],char link1[]);
void opengraph();
void doctufile(FILE *f);
int nhapsodinh(int &sodinh);
int nhaphuong(int &cohuong);
void kiemtrafile();
void kiemtrafile1();
void input(int &n,int &h,int a[][max1]);
void nhaptufile();
void set();
void indothi(int,int,int a[][max1]);
void duyetBFS();
void mophong(int);
void BFSaction(int m);
void vedtlenmanhinh(int);
void back_start();
void BFS(int s);
void BFSDQ(int s);
void basic1(int,int);
void painttop(int,int,int);
void start();
void control_program1();
/////////////////////Chi tiet chuong trinh//////////////////////////////////////
void reset_mouse1()
{
MOUSE_THERE = 0;
MOUSE_SIZE = 16;
MOUSE_VISIBLE = 0;
if (getvect(0x33) != 0L)
{
mregs.x.ax = 0;
int86(0x33, &mregs, &mregs);
if (mregs.x.ax != 0)
{
MOUSE_THERE = 1;
NUMBER_BUTTONS = mregs.x.bx;
LBUTTON_DOWN = 0;
RBUTTON_DOWN = 0;
BBUTTON_DOWN = 0;
}
}
}
void show_mouse1()
{
if (MOUSE_THERE)
{
mregs.x.ax = 1;
int86(0x33, &mregs, &mregs);
MOUSE_VISIBLE = 1;
}
}
void hide_mouse1()
{
if (MOUSE_THERE && MOUSE_VISIBLE)
{
mregs.x.ax = 2;
int86(0x33, &mregs, &mregs);
MOUSE_VISIBLE = 0;
}
}
void get_mouse_button(unsigned char *lbutton, unsigned char *rbutton, int *x, int *y)
{
if (MOUSE_THERE)
{
mregs.x.ax = 3;
int86(0x33, &mregs, &mregs);
*lbutton = (mregs.x.bx == 1) ? 1 : 0;
*rbutton = (mregs.x.bx == 2) ? 1 : 0;
if (mregs.x.bx == 3)
*rbutton = *lbutton = 1;
*x = mregs.x.cx;
*y = mregs.x.dx;
}
}
unsigned char get_button_rls_info(int butt_no, int *count, int *x, int *y)
{
if (MOUSE_THERE)
{
mregs.x.ax = 6;
mregs.x.bx = butt_no;
int86(0x33, &mregs, &mregs);
*count = mregs.x.bx;
*x = mregs.x.cx;
*y = mregs.x.dx;
if (butt_no == 0)
return (!(mregs.x.ax & 1));
else
return (!((mregs.x.ax & 2) >> 1));
}
return 0;
}
void set_new_handler(int call_mask, void (far *location)(void))
{
if (MOUSE_THERE)
{
mregs.x.ax = 12;
mregs.x.cx = call_mask;
mregs.x.dx = FP_OFF(location);
msegregs.es = FP_SEG(location);
int86(0x33, &mregs, &mregs);
}
}
void set_hide_bound(int x1, int y1, int x2, int y2)
{
if (MOUSE_THERE)
{
mregs.x.ax = 16;
mregs.x.cx = x1;
mregs.x.dx = y1;
mregs.x.si = x2;
mregs.x.di = y2;
int86(0x33, &mregs, &mregs);
}
}
void set_mouse_position(int x,int y)
{
if (MOUSE_THERE)
{
mregs.x.ax = 4;
mregs.x.cx = x;
mregs.x.dx = y;
int86(0x33, &mregs, &mregs);
}
}
void set_mouse_hlimits(int x1,int x2)
{
if (MOUSE_THERE)
{
mregs.x.ax = 7;
mregs.x.cx = x1;
mregs.x.dx = x2;
int86(0x33, &mregs, &mregs);
}
}
void set_mouse_vlimits(int y1,int y2)
{
if (MOUSE_THERE)
{
mregs.x.ax = 8;
mregs.x.cx = y1;
mregs.x.dx = y2;
int86(0x33, &mregs, &mregs);
}
}
void far new_handler(void){}
void near event_processor(int event_status, int button_status, int x, int y)
{
if ((CMX != x) || (CMY != y))
{
CURSOR_MOVED = 1;
CMX = x;
CMY = y;
}
BSTATE = button_status;
if (event_status & 2)
LBUTTON_DOWN = 1;
if (event_status & 8)
RBUTTON_DOWN = 1;
if (((event_status & 2) || (event_status & 8)) && (button_status == 3))
BBUTTON_DOWN = 1;
if ((NUMBER_BUTTONS == 3) && (event_status & 32))
BBUTTON_DOWN = 1;
if (event_status & 4)
LBUTTON_UP = 1;
if (event_status & 16)
RBUTTON_UP = 1;
if (LBUTTON_UP & RBUTTON_UP)
BBUTTON_UP = 1;
if ((NUMBER_BUTTONS == 3) && (event_status & 64))
BBUTTON_UP = 1;
}
void reset_new_handler(void)
{
CURSOR_MOVED = 0;
LBUTTON_DOWN = LBUTTON_UP = 0;
RBUTTON_DOWN = RBUTTON_UP = 0;
BBUTTON_DOWN = BBUTTON_UP = 0;
}
void install_new_handler(void)
{
if (NUMBER_BUTTONS == 3)
set_new_handler(127, new_handler)
;
else
set_new_handler(31, new_handler);
}
//============Ham hamilton 1====================
void Hamilton(int k){
int y;
for(y=0;y<sodinh1;y++)
if(a[k][y]!=0){
if((spt==sodinh1-1)&&(y==v0)){
flag=1;
return;
}
else
if(chuaxet1[y])
{
spt++;
X[spt]=y;
chuaxet1[y]=0;
Hamilton(y);
if(flag) return ;
chuaxet1[y]=1;
spt--;
}
}
}
//----------Cac ham lien quan den chuot---
//==================khoi tao ma tran ke1=========
void khoi_tao_ke1(int ke1[Max][Max])
{
int i,j;
for(i=1;i<=sodinh1;i++)
for(j=1;j<=sodinh1;j++);
ke1[i][j]=0;
}
//-----------ham tinh toa do tam thoi ban dau cua moi dinh--------
void tinhtoado(chitietdinh ctd[Max])
{
float goc;
goc=2*M_PI/sodinh1;
int r=2*getmaxx()/7;
int i;
for(i=1;i<=sodinh1;i++)
{
ctd[i].z=(midx-r*cos(i*goc));
ctd[i].o=midy-r*sin(i*goc)+30;
}
}
//Ve xong luu trong chi tiet dinh ctd[i]:i(1-n:so dinh)
//------ve mot dinh-----------
void ve_dinh(int chiso,int x, int y) //x,y la toa do cua dinh
{
char s[1]="";
setcolor(10);
circle(x,y,10);
floodfill(x,y,10);
setcolor(RED);
itoa(chiso,s,10);
settextjustify(1,1);
outtextxy(x,y,s);
}
//=============ham ve canh==========
void in_dinh(int chiso,int x,int y)
{
char s[1]="";
setcolor(WHITE);
itoa(chiso,s,10);
settextjustify(1,1);
outtextxy(x,y,s);
}
//----------------------------------
void ve_canh(int ke1[Max][Max])
{
int i,j;
for(i=1;i<=sodinh1;i++)
for(j=1;j<=sodinh1;j++)
if(ke1[i][j]==1)
{
line(ctd[i].z,ctd[i].o,ctd[j].z,ctd[j].o);
setcolor(13);
circle(abs(ctd[i].z+ctd[j].z)/2,abs(ctd[i].o+ctd[j].o)/2,2);
floodfill( (ctd[i].z+ctd[j].z)/2,(ctd[i].o+ctd[j].o)/2,13);
}
}
//-------------ham dua ra dang do thi ban dau-------------
void vedothibandau(chitietdinh ctd[])
{
int i,j;
rectangle(0,5,636,479);
rectangle(2,7,634,477);
cleardevice();
for(i=1;i<=sodinh1;i++)
{
ve_dinh(i,ctd[i].z,ctd[i].o);
}
ve_canh(ke1);
show_mouse1();
}
//======================xoa dinh===========
void xoadinh(int chisodinh1)
{
int i,j,k;
for(i=chisodinh1;i<=sodinh1;i++)
for(j=1;j<=sodinh1;j++)
{
ke1[i][j]=ke1[i+1][j];
ke1[j][i]=ke1[j+1][i];
}
for(k=chisodinh1;k<=sodinh1;k++)
{
ctd[k].z=ctd[k+1].z;
ctd[k].o=ctd[k+1].o;
}
sodinh1--;
}
//------------Xoa canh-------------------
void xoa_canh(int chiso1,int chiso2)
{
ke1[chiso1][chiso2]=0;
ke1[chiso2][chiso1]=0;
}
//-------------Them dinh moi----------
void them_dinh(long x,long y)
{ int i;
sodinh1++;
ctd[sodinh1].z=x;
ctd[sodinh1].o=y;
for(i=1;i<=sodinh1;i++)
{
ke1[sodinh1][i]=0;
ke1[i][sodinh1]=0;
}
}
//------------ham kiem tra toa do chuot co thuoc dinh nao khong----------
int xy_danhsachdinh(long x, long y, chitietdinh d[Max],int sodinh1,int &chiso)
{
int i;
for(i=1;i<=sodinh1;i++)
if( ( (x-d[i].z)*(x-d[i].z) + (y-d[i].o)*(y-d[i].o)) <=400)
{
chiso=i;
return 1;
}
return 0;
}
//==============kiem tra xy thuoc canh============
int xy_danhsachcanh(long x,long y,int &chiso1,int &chiso2)
{
int i,j;
for(i=1;i<sodinh1;i++) {
for(j=i+1;j<=sodinh1;j++)
if((ke1[i][j]==1)&&( bp(x-(ctd[i].z+ctd[j].z)/2)+ bp(y-(ctd[i].o+ctd[j].o)/2)) <100 )
{ chiso1=i;
chiso2=j;
return 1;
}
}
return 0;
}
//-----------cho su kien cua chuot||ban phim------------
void sukien(int &banphim,int &chuottrai,int &chuotphai)
{
setcolor(7);
rectangle(0,5,636,479);
rectangle(2,7,634,477);
show_mouse1();
banphim=0;
do
{
get_mouse_button(&lm,&rm,&xm,&ym);
} while(!kbhit() && !lm && !rm);
x1=xm;
y1=ym;
if(kbhit())
banphim=getch();
chuottrai=lm;
chuotphai=rm;
while (lm||rm)
{
get_mouse_button(&lm,&rm,&xm,&ym);
}
x2=xm;
y2=ym;
hide_mouse1();
}
//---------------ham di chuyen dinh--------------
void di_chuyen_dinh(chitietdinh ctd[Max],int chiso,float x, float y)
{
ctd[chiso].z=x;
ctd[chiso].o=y;
}
//========================================
//========================Nhap text==================
void nhapchuoi(int x, int y,char *tentt)
{
char ch;
tentt[0]=NULL;
settextjustify(0,1);
do
{
ch=getch();
if ((97<=ch && ch<=122) || (14<=ch && ch<=95)|| ch==126)
{
tentt[strlen(tentt)+1]=NULL;
tentt[strlen(tentt)]=ch;
}
if (ch==8)
{
setcolor(BLACK);
outtextxy(x,y,tentt);
tentt[strlen(tentt)-1]=NULL;
}
if (ch==27)
{
tentt[0]=27;
tentt[1]=NULL;
ch=13;
}
setcolor(10);
outtextxy(x,y,tentt);
}
while (ch!=13);
}
//==============case 1===================
void case1()
{
char *file;
FILE *f;
char *pt;
//------------------------------------------------
//Khoi tao che do do hoa
cleardevice();
setcolor(7);
rectangle(0,5,636,479);
rectangle(2,7,634,477);
fflush(stdin);
setcolor(WHITE);
outtextxy(120,20,"------CHUONG TRINH TIM CHU TRINH HAMILTON------");
outtextxy(120,40,"----------TU DO THI CO SAN TRONG FILE----------");
outtextxy(180,60,"---------===(-<.>-)===---------");
setcolor(CYAN);
outtextxy(30,90,"Huong dan :");
line(25,100,30+textwidth("Huong dan :"),100);
setcolor(YELLOW);
outtextxy(30,110,"1.Nhap vao ten file co chua ma tran ke1.");
outtextxy(30,130,"2.Kiem tra ma tran dau vao.");
outtextxy(30,150,"3.Mo phong dang do thi nhap vao.");
outtextxy(30,170,"4.Tim va in ra chu trinh hamilton neu co.");
setcolor(WHITE);
outtextxy(180,185,"---------===(-<.>-)===---------");
setcolor(CYAN);
outtextxy(30,200,"Nhap vao ten file : ");
line(25,210,30+textwidth("Nhap vao ten file :"),210);
setcolor(10);
nhapchuoi(30+textwidth("Nhap vao ten file : "),204,file);
outtextxy(30,220,"Search ");
for(i=0;i<6;i++)
{
outtextxy(30+textwidth("Search ")+4*i,220,".");
delay(500);
}
f=fopen(file,"r");
if(f==NULL)
{
outtextxy(30+textwidth("Search......"),220,"==> Khong tim thay file! ");
outtextxy(30,460,"Exit ");
for(i=0;i<6;i++)
{
outtextxy(30+textwidth("Exit ")+4*i,460,".");
delay(500);
}
return;
}
else outtextxy(30+textwidth("Search......"),220,"==> Da tim thay file ! ");
//Kiem tra ma tran ke1 nhap vao
outtextxy(30,240,"Kiem tra ma tran nhap vao ");
for(i=0;i<6;i++)
{
outtextxy(30+textwidth("Kiem tra ma tran nhap vao ")+4*i,240,".");
delay(500);
}
fscanf(f,"%d",&sodinh1);
for(i=0;i<sodinh1;i++)
for(j=0;j<sodinh1;j++)fscanf(f,"%d",&a[i][j]);
for(i=0;i<sodinh1;i++)
for(j=0;j<sodinh1;j++)if(a[i][j]!=a[j][i])
{
kt=0;
break;
}
if(kt==1)
{
outtextxy(30,260,"==> Ma tran nhap vao thoa yeu cau ! ");
outtextxy(30,460,"Waiting ");
for(i=0;i<6;i++)
{
outtextxy(30+textwidth("Waiting ")+4*i,460,".");
delay(500);
}
}
else
{
outtextxy(30,260,"==> Ma tran nhap vao khong thoa yeu cau ! ");
outtextxy(30,460,"Exit ");
for(i=0;i<6;i++)
{
outtextxy(30+textwidth("Exit ")+4*i,460,".");
delay(500);
}
return ;
}
//================Thiet lap chu trinh hamilton==============
for(i=0;i<sodinh1;i++) chuaxet1[i]=1;
v0=0;
spt=0;
chuaxet1[v0]=0;
flag=0;
Hamilton(v0);
//closegraph();
//----------------------------------------------------
//Ve do thi luc dau
//----------------------------------------------------
cleardevice();
setcolor(7);
rectangle(0,5,636,479);
rectangle(2,7,634,477);
setcolor(WHITE);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -