Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <windows.h>
- //設定全域數值
- #define FILE_MAP "input_map.txt"
- #define FILE_OUTPUT "output_route.txt" //人機輸出
- #define MAP_MAXSIZE_X 100
- #define MAP_MAXSIZE_Y 100
- #define MAX_STACK (MAP_MAXSIZE_X*MAP_MAXSIZE_Y)/2
- #define bool int
- #define true 1
- #define false 0 //設定參數
- int max_x=0, max_y=0;
- char map[MAP_MAXSIZE_X][MAP_MAXSIZE_Y]={1};
- bool passed[MAP_MAXSIZE_X][MAP_MAXSIZE_Y]={0}; //設定初始值
- struct _POSITION // 設定座標結構
- {
- int x;
- int y;
- };
- typedef struct _POSITION POSITION;
- POSITION stack[MAX_STACK]; //堆疊數據
- int top = -1; //最頂堆疊數據
- //如果堆疊是空的
- bool Empty()
- {
- if(top == -1)
- return true;
- return false;
- }
- // 如果堆疊是滿的
- bool Full()
- {
- if(top < MAX_STACK-1)
- return false;
- return true;
- }
- // 從堆疊跳出
- POSITION Pop()
- {
- return stack[top--];
- }
- // 把數據寫入堆疊
- void Push(POSITION posData)
- {
- stack[++top]=posData;
- }
- void run(int x, int y)
- {
- FILE *fptr;
- POSITION last; //最後坐標資訊
- unsigned int branch = 0; //分支碼
- int direction = 1; // 1:東 2:南 3:西 4:北
- fptr = fopen(FILE_OUTPUT, "w");
- while(map[x][y] != 'O') //達到目標前持續做
- {
- branch = 0; // 分支數據清零
- passed[x][y] = 1; // 設定此位置可通過
- // 指令:選一條路走
- if((y+1<max_y) && ((map[x][y+1] == 'O') || (map[x][y+1] == '0')) // 假如東方可以過(尚未過去)
- && (passed[x][y+1] == 0))
- {
- branch++; // 增加分支(假如這可以過)
- direction = 1;
- }
- if((x+1<max_x) && ((map[x+1][y] == 'O') || (map[x+1][y] == '0')) // 假如西方可以過(尚未過去)
- && (passed[x+1][y] == 0))
- {
- branch++; // 增加分支(假如這可以過)
- direction = 2;
- }
- if((y-1>=0) && ((map[x][y-1] == 'O') || (map[x][y-1] == '0')) // 假如南方可以過(尚未過去)
- && (passed[x][y-1] == 0))
- {
- branch++; // 增加分支(假如這可以過)
- direction = 3;
- }
- if((x-1>=0) && ((map[x-1][y] == 'O') || (map[x-1][y] == '0')) // 假如北方可以過(尚未過去)
- && (passed[x-1][y] == 0))
- {
- branch++; // 增加分支(假如這可以過)
- direction = 4;
- }
- // 指令:前進
- if(branch > 1) //假如分支不只一個
- {
- if(!Full()) // 假如堆疊不是滿的(把分支寫入堆疊)
- {
- last.x = x;
- last.y = y;
- Push(last);
- printf("Push(%d,%d), ", last.x+1, last.y+1);
- fprintf(fptr, "Push(%d,%d), ", last.x+1, last.y+1);
- }
- }
- else if(branch == 0) // 假如不能通過
- {
- printf("遇到死路, ");
- fprintf(fptr, "遇到死路, ");
- if(!IsEmpty())
- {
- last = Pop();
- x = last.x;
- y = last.y;
- printf("(%d,%d) = Pop(), ", last.x+1, last.y+1);
- fprintf(fptr, "(%d,%d) = Pop(), ", last.x+1, last.y+1);
- }
- else
- {
- printf("無法離開\n");
- fprintf(fptr, "無法離開\n");
- fclose(fptr);
- return;
- }
- continue;
- }
- //指令:在最後的方向選擇一種方式前進
- switch(direction) //fptr:輸出檔案用
- { //printf:人機
- case 1:
- y = y + 1;
- printf("右, ");
- fprintf(fptr, "右, ");
- break;
- case 2:
- x = x + 1;
- printf("下, ");
- fprintf(fptr, "下, ");
- break;
- case 3:
- y = y - 1;
- printf("左, ");
- fprintf(fptr, "左, ");
- break;
- case 4:
- x = x - 1;
- printf("上, ");
- fprintf(fptr, "上, ");
- break;
- }
- }
- printf("到達\n");
- fprintf(fptr, "到達\n");
- fclose(fptr);
- }
- int main()
- {
- FILE *fptr;
- int i,j,start_x,start_y;
- // 指令:加載文件
- fptr = fopen(FILE_MAP,"r");
- if(!fptr)
- {
- printf("File loaded error!\n");
- return 0;
- }
- // 指令:讀取文件
- fscanf(fptr, "%d %d\n",&max_x, &max_y);
- if(max_x==0 || max_y==0)
- return 0;
- for(i=0;i<max_x;i++)
- {
- for(j=0;j<max_y;j++)
- {
- fscanf(fptr, " %c", &map[i][j]);
- passed[i][j]=0;
- if(map[i][j]=='M')
- {
- start_y=i;
- start_x=j;
- }
- }
- }
- fclose(fptr);
- // 指令:匯出迷宮圖
- for(i=0;i<max_x;i++)
- {
- for(j=0;j<max_y;j++)
- {
- printf("%c ", map[i][j]);
- }
- printf("\n");
- }
- run(start_y,start_x); // 跑迷宮
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement