⑴ 急！急！急！如何用c語言編寫一個走迷宮的游戲
#include<stdio.h>櫻彎
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<graphics.h>扒睜
#define x1 (a-120)/脊此悶20
#define y1 (b-40)/20
#define UP 72
#define DOWN 80
#define LEFT 75
#define RIGHT 77
#define ENTER 13
#define ESC 27
int d[21][21]={0};
int a=120,b=40;
void init()
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"d:\\tc20");
}
void drawlist()
{
int i,j;
setbkcolor(BLACK);
setcolor(RED);
for(i=0,j=0;i<=20,j<=20;i++,j++)
{
line(i*20+120,40,i*20+120,440);
line(120,40+20*j,520,40+20*j);
}
}
void drawfirst()
{
gotoxy(120,40);
setcolor(YELLOW);
circle(120+10,40+10,6);
setfillstyle(1,BROWN);
floodfill(120+10,40+10,YELLOW);
}
void clearold(int m,int n)
{
setfillstyle(1,BLACK);
floodfill(m+10,n+10,YELLOW);
setcolor(BLACK);
circle(m+10,n+10,6);
}
void drawnew(int m,int n)
{
setcolor(YELLOW);
circle(m+10,n+10,6);
setfillstyle(1,BROWN);
floodfill(m+10,n+10,YELLOW);
}
void filllist()
{
int i,j,t,m;
randomize();
for(i=0;i<=18;i++)
for(j=1;j<=19;j++)
{ t=random(2)
if(t==1)
{
setfillstyle(1,1);
floodfill(121+20*i,41+20*j,RED);
d[i][j]=1;}
else d[i][j]=0;
}
d[0][0]=0;d[19][19]=0;
setfillstyle(1,BLACK);
floodfill(121,41,RED);
floodfill(121+19*20,41+19*20,RED);
}
void getway()
{
int flag=1;
while(flag==1)
{
gotoxy(a,b);
for(;b<=440&&a<=520&&a>=120&&b>=40;)
{
switch(getch())
{
case UP : {
if(b==40);
else if(d[(b-40)/20-1][(a-120)/20]==0)
{clearold(a,b);gotoxy(a,b=b-20);drawnew(a,b);}
else;
break;}
case DOWN:{
if(b==440);
else
if(d[(b-40)/20+1][(a-120)/20]==0){clearold(a,b);gotoxy(a,b=b+20);drawnew(a,b);}else;
break; }
case RIGHT : {
if(b==520);
else
if(d[(b-40)/20][(a-120)/20+1]==0){clearold(a,b);gotoxy(a=a+20,b);drawnew(a,b);}else;
break; }
case LEFT : {
if(b==120);
else
if(d[(b-40)/20][(a-120)/20-1]==0){clearold(a,b);gotoxy(a=a-20,b);drawnew(a,b);}else;
break;}
case ESC : exit();break;
default : break;
if(a==500&&b==420)break;
}/*switch finish*/
}/*for finish*/
}/*while finish*/
}
void main()
{
init();
drawlist();
filllist();
drawfirst();
getway();
getch();
closegraph();
}
⑵ c語言數字迷宮問題怎麼做圖片如下
可以參考八皇後問題用回溯的方式來解決。
這道迷宮題，觀察一下，與某個格子相鄰的格子至多為4個，也就是有4種可能的前進方向，需要窮舉所有可能。在窮舉下一種可能前，需要恢復初始狀態（即回溯）。寫了一個簡單的代碼，還有很多需要優化的地方，但關鍵是能用^_^，你可以調試一下，把實現的思路寫出來，就可以順利完成這道題了。
#include <stdio.h>
#include <string.h>
/***
1、 迷宮大小n*n，擴展為(n+2)*(n+2)，外圍一圈的格子作為不可再前進的邊界。
2、 若所有相鄰格子均已訪問，表明此路不通，回溯。
3、 計數器達到總步數，檢查是否位於終點及中間路徑是否合法，通過則顯示。
4、 查找函數Lookup()以遞歸方式反復調用自身，a->b->c->...，以查找某條可能的路徑。
...c,b,a等返回前，均回溯，逐步恢復tag。
離開a時，tag已經恢復到初始狀態，如此就不影響查找其他路徑了。
5、 若迷宮夠大或數據特別，都可能存在不同的路線
6、 先查看main()，了解基本步驟及初始化過程
***/
const int N = 6;
// eg1. N = 6
int row[N] = { 0, 4, 3, 1, 3, 0}; // 4 + 3 + 1 + 3 = 11
int col[N] = { 0, 1, 4, 3, 3, 0};
// eg2. N = 6
//int row[N] = { 0, 3, 4, 4, 2, 0}; // 3 + 4 + 4 + 2 = 13
//int col[N] = { 0, 3, 2, 4, 4, 0};
// eg3. N = 8
//int row[N] = { 0, 3, 1, 4, 3, 3, 1, 0};
//int col[N] = { 0, 1, 1, 5, 3, 1, 4, 0};
// 計數器
// Lookup()用g_counter與COUNTER比較是否走到了規定的步數
int g_counter = 0; // 無論是否成功，每查找一條路徑後自動恢復為0
int COUNTER = 0; // 總步數，等於row（或col）數組各元素之和，在main()中初始化
// Lookup()用tag記錄行走狀況
// 在main()中初始化
// 每查找一條路徑後自動恢復為初始狀態
struct _tag
{
int row[N];
int col[N];
int arr[N][N]; // 走過，按順序標記
} tag;
// 顯示迷宮
// inside為false時，列印擴展的迷宮
// inside為true時，列印未擴展的迷宮
void Display(bool inside)
{
int i, j;
for (i = 0; i < N; i++)
{
if ((i == 0 || i == N-1) && inside)
continue;
for (j = 0; j < N; j++)
{
if ((j == 0 || j == N-1) && inside)
printf("%4s", " ");
else
printf("%4d", tag.arr[i][j]);
}
printf(" ");
}
printf(" ");
}
// 檢查路徑是否符合已給條件
bool Check()
{
bool b = true;
int sum_row, sum_col;
for (int i = 1; i < N-1; i++)
{
sum_row = 0;
sum_col = 0;
for (int j = 1; j < N-1; j++)
{
sum_row += tag.arr[i][j] > 0 ? 1 : 0;
sum_col += tag.arr[j][i] > 0 ? 1 : 0;
}
if (sum_row != row[i] || sum_col != col[i])
{
b = false;
break;
}
}
return b;
}
// 遞歸查找路徑，返回前擦除痕跡，恢復現場
// 當前訪問的格子(i,j)，i:行坐標，j:列坐標
void Lookup(int i, int j)
{
g_counter++; // 總步數加1
tag.arr[i][j] = g_counter; // visited
tag.row[i]--; // 行計數減1
tag.col[j]--; // 列計數減1
// 走完了
if (g_counter >= COUNTER)
{
// 位於終點，且路徑合法
if (i == N-2 && j == N-2 && Check())
{
Display(true);
}
// 此格子已判別，恢復現場，以查找其他路徑（此即回溯的思想）
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
return;
}
// 行方向
if (tag.row[i] > 0)
{
if (!tag.arr[i][j+1])
{
Lookup(i, j+1); // 從當前格子向右走一步
}
if (!tag.arr[i][j-1])
{
Lookup(i, j-1); // 從當前格子向左走一步
}
}
// 列方向
if (tag.col[j] > 0)
{
if (!tag.arr[i+1][j])
{
Lookup(i+1, j); // 從當前格子向下走一步
}
if (!tag.arr[i-1][j])
{
Lookup(i-1, j); // 從當前格子向上走一步
}
}
// 此格子已判別，恢復現場，以查找其他路徑（此即回溯的思想）
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
}
int main()
{
// 格子初始化為全0
memset(tag.arr, 0, sizeof(tag.arr));
for (int i = 0; i < N; i++)
{
tag.row[i] = row[i];
tag.col[i] = col[i];
COUNTER += row[i];
tag.arr[0][i] = 1;
tag.arr[N-1][i] = 1;
tag.arr[i][0] = 1;
tag.arr[i][N-1] = 1;
}
printf("初始化: ");
Display(false);
printf("合法路徑: ");
Lookup(1, 1); // 從格子(1, 1)出發
//getchar();
return 0;
}
⑶ 如何用C語言編寫一個迷宮程序
#include
⑷ 12345迷宮的三種解法
遞歸求解、回溯求解和隊列求解。迷宮求解是c語言編程蘆裂中的數學題，有三種解題方法分別是遞歸求解、回溯求解和隊列求解，其中在回溯解法中，主要是用棧纖燃來存儲可以探索的位置，利用棧後進先出的特點，在一條分路上探索失敗時，回到最近一次存儲的可探索位置，這是一種深度毀嘩虛優先搜索的方法。
⑸ 如何用C語言編寫一個迷宮程序
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};
struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/
int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*************建立迷宮*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宮行,列 [/M]
printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為(最外圈為強)...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北 [/M]
initmaze(sto);//建立迷宮
printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
⑹ 用C語言編寫一個迷宮程序，知道出處也行 ~~！
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};
struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行迅枯核,y列
int d; //d下一步的方向
};
typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/
int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一敗陪個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置畝掘入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*************建立迷宮*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宮行,列 [/M]
printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為(最外圈為強)...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北 [/M]
initmaze(sto);//建立迷宮
printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
⑺ 回溯法的用回溯法解題的一般步驟
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先方式搜索解賀腔空間，並在搜索過程中用剪枝函數避免無效搜索。
回溯法C語言舉例
八皇後問題是能用回溯法解決的一個經典問題。
八皇後問題是一個古老而著名的問題。該問銷差題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一對角線上，問有多少種擺法。引入一個整型一維數組col[]來存放最終結果，col[i]就表示在棋盤第i列、col[i]行有一個皇後，為了使程序再找完了全部解後回到最初位置，設定col[0]的初值為0，即當回溯到第0列時，說明以求得全部解，結束程序運行。為了方便演算法的實現，引入三個整型數組來表示當前列在三個方向上禪斗衫的狀態 ：
a[] a[i]=0表示第i行上還沒有皇後；
b[] b[i]=0表示第i列反斜線/上沒有皇後；
c[] c[i]=0表示第i列正斜線上沒有皇後。
棋盤中同一反斜線/上的方格的行號與列號之和相同；同一正斜線上的方格的行號與列號之差均相同，這就是判斷斜線的依據。
初始時，所有行和斜線上都沒有皇後，從第1列的第1行配置第一個皇後開始，在第m列，col[m]行放置了一個合理的皇後，准備考察第m+1列時，在數組a[]，b[]和c[]中為第m列，col[m]行的位置設定有皇後的標志；當從第m列回溯到m-1列時，並准備調整第m-1列的皇後配置時，清除在數組a[],b[]和c[]對應位置的值都為1來確定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇後問題的皇後所在每一行位置，從1開始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are:
);
while(not_finish) //not_finsh=1:處理未結束
{
while(not_finish && i<Queens+1) //處理未結束
{
for(flag=1,k=1;flag && k<i;k++)//判斷是否有多個皇後在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判斷是否有多個皇後在對角線
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重設第i個元素
{
if(a[i]==a[i-1]) //若a[i]的值已經已經一圈追上a[i-1]的值
{
i--; //退回一步 重新試探處理前一個元素
if(i>1 && a[i]==Queens)
a[i]=1; // 當a[i]為 Queens時 將a[i]的值重置
else
if(i==1 && a[i]==Queens)//當第一未位的值達到Queens時結束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一個元素的值為Queens
if(a[i-1]==Queens)
a[i]=1;
else //否則元素為前一個元素的下一個值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]::
[%2d]:,count);
for(k=1;k<=Queens;k++) //輸出結果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通過路徑用數字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf(
);
}
system(pause);
return 0;
}
回溯法解決迷宮問題PASCAL語言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.
⑻ C語言編程求解啊！利用回溯演算法的迷宮搜索類型問題
#include "stdafx.h"
#include <iostream>
#include "cmath"
#include <fstream>
using namespace std ;
int ROW ;
int COL ;
int **g_pRoom ;
// 回溯法注意標記已訪問過的節點。。。。。不然就會進入重復操作將棧用空。。。。。。。。
struct Point
{
Point( int xx = 0, int yy = 0 ):x(xx),y(yy) { }
int x ;
int y ;
} ;
int g_nMax = 0 ;
Point g_pResult[100] ;
int g_nCount ;
Point g_pStart ;
Point g_pEnd ;
Point g_pOrient[4] = { Point(-1, 0 ) , Point( 0 ,1 ) , Point( 1 ,0 ) , Point( 0 , -1 ) } ;
bool Read_data( ifstream &file )
{
if( file.eof() )
return false ;
g_nMax = 0 ;
g_nCount = 0 ;
file>>ROW>>COL ;
g_pRoom = new int*[ROW] ;
g_pStart = g_pEnd = Point( -1, -1 ) ;
for( int i = 0 ; i < ROW ; i++ )
g_pRoom[i] = new int[COL] ;
for( int i = 0 ; i < ROW ; i++ )
for( int j = 0 ; j < COL ; j++ )
{
file>>g_pRoom[i][j] ;
if( g_pRoom[i][j] == -1 )
{
g_pStart.x = j ;
g_pStart.y = i ;
}
else if( g_pRoom[i][j] == -2 )
{
g_pEnd.x = j ;
g_pEnd.y = i ;
}
}
if( g_pStart.x == -1 || g_pEnd.x == -1 )
{
cout<<" the data errror !\n" ;
return false ;
}
return true ;
}
void Dateback( Point pStart )
{
static Point Stack[1000] ;
static int nTop = 0 ;
static int Apple = 0 ;
if( pStart.x == g_pEnd.x && pStart.y == g_pEnd.y )
{
if( Apple + 2 > g_nMax )
{
g_nMax = Apple + 2 ;
for( int i = 0 ; i < nTop ; i++ )
g_pResult[i] = Stack[i] ;
g_nCount = nTop ;
} // ....
}
else
{
for( int i = 0 ; i < 4 ; i++ )
{
Point s ;
s.x = pStart.x + g_pOrient[i].x ;
s.y = pStart.y + g_pOrient[i].y ;
if( s.x >= 0 && s.x < COL && s.y >= 0 && s.y < ROW && g_pRoom[s.y][s.x] != 0 )
{
Apple += g_pRoom[s.y][s.x] ;
Stack[nTop++] = s ;
int temp = g_pRoom[s.y][s.x] ;
g_pRoom[s.y][s.x] = 0;
Dateback( s ) ;
nTop-- ;
g_pRoom[s.y][s.x] = temp ;
Apple -= g_pRoom[s.y][s.x] ;
}
}
}
}
int main()
{
ifstream file("data.txt") ;
Read_data(file) ;
Dateback( g_pStart ) ;
cout<<g_nMax ;
cout<<"("<<g_pStart.y<<","<<g_pStart.x<<")"<<" " ;
for( int i = 0 ; i < g_nCount ; i++ )
cout<<"("<<g_pResult[i].y<<","<<g_pResult[i].x<<")"<<" " ;
return 0 ;
}
⑼ 數據結構迷宮問題（c語言）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(&t));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(num<m*n/2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d ",map[i][j]);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i<4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;i<ans;i++)
printf("(%d,%d)\n",a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}
⑽ C語言 棧 迷宮 的一個疑問
全部程序分幾個文件，看清楚了，每段程序放入一個文件，每段程序前面都有文件名： //stackoperation.cpp Status InitStack(SqStack &S) { //構造一個空棧S S.base = (SElemType *)malloc(RANGE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存儲分配失敗 S.top = S.base; S.stacksize = RANGE; return OK; }//Initstack Status Push(SqStack &S,SElemType e) { //插入元素e為新的棧頂元素 if(S.top - S.base >= S.stacksize){//棧滿，追加存儲空間 S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存儲分配失敗 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; }//Push Status Pop(SqStack &S,SElemType &e){ /*若棧不空，則刪除S的棧頂元素，用e返回其值，並返回OK； 否則返回迅液ERROR*/ if(S.top == S.base) return ERROR; e = * --S.top; return OK; }//Pop bool StackEmpty(SqStack S) { //判斷棧是否為空並返回TURN或FALSE if(S.top == S.base) return TURE; return FALSE; }//StackEmpty void PrintStack() { SqStack ST; SElemType e; InitStack(ST); do{ Pop(SqS,e); Push(ST,e); }while(!StackEmpty(SqS)); do{ Pop(ST,e); printf("(%d,%d,%d)",e.seat.i,e.seat.j,e.di); }while(!StackEmpty(ST)); } //migong.cpp #include "Basetype.h" #include "stackoperation.cpp" #include "Mazeoperation.cpp" void main() { char filename[15]; FILE *fp; printf("請輸入迷宮數據文件名（長度不超過15個字元）："); scanf("%s",&filename); //如檔茄找不到文件，則要求重新輸入（最多三次機會） for(int i=0;i<3;i++){ if((fp = fopen(filename,"r")) == NULL) {printf("不能打開文件,請重新輸入文件名（長度不超過15個字元）：\n"); scanf("%s",filename); }//if break; }//for //讀取迷宮的行數和列數 int rnum,cnum; fscanf(fp,"%d,%d",&rnum,&cnum); printf("這個迷宮有%d行，%d列\n",rnum,cnum); if(rnum>RANGE-2 || cnum>RANGE-2) { printf("迷宮太大，無法求解\n"); return; }//判斷迷宮的大小是否符合要求 //初始化一個迷宮變數 MazeType maze; for(i=0;i<=rnum+1;i++) for(int j=0;j<=cnum+1;j++) maze.arr[i][j] = '#'; CreatMaze(maze,rnum,cnum,fp);//創建迷宮 fclose(fp);//關閉迷宮文件 //列印當前迷宮 printf("當前迷宮為：\n"); for(i=0;i<=rnum+1;i++) { for(int j=0;j<=cnum+1;j++) printf("%c",maze.arr[i][j]); printf("\n"); } printf("其畝蠢物中'#'表示障礙,外圍一圈'#'為圍牆\n"); //讀取入口及出口位置 PosType startp,endp; printf("請輸入入口位置（兩數中間以逗號相隔）："); scanf("%d,%d",&startp.i,&startp.j); printf("請輸入出口位置（兩數中間以逗號相隔）："); scanf("%d,%d",&endp.i,&endp.j); if(MazePath(maze,startp,endp)) { PrintMaze(maze,rnum,cnum);//將求解的迷宮輸出到文件保存，並列印到屏幕 PrintStack();//如果存在路徑則列印之 } else printf("此迷宮不存在路徑\n"); }//main //Mazeoperation.cpp bool Pass(MazeType maze,PosType curpos) { //判斷當前位置是否可通，並返回值 switch(char ch = maze.arr[curpos.i][curpos.j]) { case' ': return(FALSE); case'#': case'@': case'*': return(TURE); default: { printf("迷宮中第%d行,第%d列出現不明字元%c\n", curpos.i,curpos.j,ch);exit(0);} }//switch }//pass void FootPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '*'; }//FootPrint void MarkPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '@'; }//MarkPrint void NextPos(PosType &curpos,int di) { switch(di) { case 1: curpos.j++;break; case 2: curpos.i++;break; case 3: curpos.j--;break; case 4: curpos.i--;break; default: printf("當前方向%d無效\n",di); exit(0); }//switch }//NextPos bool MazePath(MazeType &maze,PosType start,PosType end){ SElemType e; InitStack(SqS); PosType curpos = start; int curstep = 1; do{ if(!Pass(maze,curpos)){ FootPrint(maze,curpos); e.order = curstep; e.seat.i = curpos.i;e.seat.j = curpos.j; e.di = 1; Push(SqS,e); if(curpos.i == end.i && curpos.j == end.j) return(TURE); NextPos(curpos,1); curstep++; }//if else{ if(!StackEmpty(SqS)){ Pop(SqS,e); while(e.di == 4 && !StackEmpty(SqS)){ MarkPrint(maze,e.seat); Pop(SqS,e); }//while if(e.di<4){ e.di++; Push(SqS,e); NextPos(e.seat,e.di); curpos.i = e.seat.i;curpos.j = e.seat.j; }//if }//if }//else }while(!StackEmpty(SqS)); return(FALSE); }//Mazepath void CreatMaze(MazeType &maze,int row,int col,FILE *fp){ //建立迷宮 char ch = fgetc(fp); for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) {switch( ch = fgetc(fp)) { case'0': maze.arr[i][j]=' ';break; case'1': maze.arr[i][j]='#';break; default: printf("迷宮第%d行第%d列數據為%c有錯誤",i,j,ch);exit(0); }//switch }//for fseek(fp,2,1); }//for fclose(fp); }//CreatMaze void PrintMaze(MazeType maze,int row,int col) { //列印結果並輸出到文件保存 FILE *out; if((out = fopen("outfile","w"))==NULL) { printf("不能打開文件\n"); exit(0); }//if for(int i=0;i<=row+1;i++) {for(int j=0;j<=col+1;j++) { fputc(maze.arr[i][j],out); printf("%c",maze.arr[i][j]); } printf("\n"); } printf("其中'*'號代表路徑，'#'代表障礙,'@'代表死胡同\n"); fclose(out);//關閉文件 } //Basetype.h #include <stdio.h> #include "stdlib.h" #define RANGE 30 //棧的存儲空間初始分配量， //以及用來存放迷宮的字元數組的最大維數 #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACKINCREMENT 5 //棧的存儲空間分配增量 typedef struct{ int i; //行坐標 int j; //列坐標 }PosType; //迷宮中坐標位置類型 //棧的定義 typedef struct{ int order; //通道塊在路徑上的「方向」 PosType seat; //通道塊在迷宮中的「坐標位置」 int di; //從此通道塊走向下一通道塊的「方向」 }SElemType; //棧的元素類型 typedef struct{ SElemType *base; //棧底指針 SElemType *top; //棧頂指針 int stacksize; //當前已分配的存儲空間，以元素為單位 }SqStack; //迷宮的定義 typedef struct{ int m,n; char arr[RANGE][RANGE]; }MazeType; typedef int Status; SqStack SqS; //定義一個棧 ~