摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

這是屬於BFS+DP(?)
第1次模擬BFS好High 不過我不會用指標之類的
簡單的說明:首先先找出第1步 然後在它的附近標上走到的最小步數(如果可以走的話) 然後再將此點放入陣列中 作為下一次的尋找對象

老實說 我是因為曾經一度放棄資訊 很不爽
要開始說囉
1.K的旁邊如果可以走而且沒有其他路走過 就為現在這格步數再往前+1 並加入佇列之中 作為下次走訪的資料
2.然後 如果抓到老鼠的話 就可以結束了
基本上我跟別人的作法不太一樣 還蠻複雜的 別人的都好厲害...
看圖應該就可以了解吧
這是一張基本的圖 (神秘的黑線不要理)
######################################################
#..................@.................................#
#..................###########.......................#
#..................#.........#.......................#
#..................#...K.....#@......................#
#.....@............#.........#.......................#
#..................#######..##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#...1.....#.......................#
#..................#..1K1....#@......................#
#.....@............#...1.....#.......................#
#..................#######..##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#..212....#.......................#
#..................#.21K12...#@......................#
#.....@............#..212....#.......................#
#..................#######..##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#.32123...#.......................#
#..................#321K123..#@......................#
#.....@............#.32123...#.......................#
#..................#######..##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#4321234..#.......................#
#..................#321K1234.#@......................#
#.....@............#4321234..#.......................#
#..................#######..##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#43212345.#.......................#
#..................#321K12345#@......................#
#.....@............#43212345.#.......................#
#..................#######5.##.......................#
#........................#..#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#432123456#.......................#
#..................#321K12345#@......................#
#.....@............#432123456#.......................#
#..................#######56##.......................#
#........................#6.#........................#
#....................................................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#432123456#.......................#
#..................#321K12345#@......................#
#.....@............#432123456#.......................#
#..................#######56##.......................#
#........................#67#........................#
#.........................7..........................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#432123456#.......................#
#..................#321K12345#@......................#
#.....@............#432123456#.......................#
#..................#######56##.......................#
#........................#67#........................#
#........................878.........................#
######################################################
↓
######################################################
#..................@.................................#
#..................###########.......................#
#..................#432123456#.......................#
#..................#321K12345#@......................#
#.....@............#432123456#.......................#
#..................#######56##.......................#
#........................#67#........................#
#.......................98789........................#
######################################################
.
.
.

/************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char x[102];
main()
{
 int n,m,a,b,ii,jj;
 while(scanf("%d",&n)==1&&n!=0)
   {
    int map[101][101]={0};
    for(a=0;a<n;a++)
     {
       scanf("%s",x);
       m=strlen(x);
       for(b=0;b<m;b++)
        {
         if(x[b]=='#') map[a][b]=-1;
         if(x[b]=='@') map[a][b]=-2;
         if(x[b]=='K') {ii=a;jj=b;} 
        }
     }
     /*圖形牆壁為-1 老鼠為-2 起始點不採用標記 原因:複雜化了*/
     int stack[10001][2]={0},top=0;
     int ans=0;
     stack[0][0]=ii;stack[0][1]=jj;
     for(a=0;a<=top;a++)
      {
        int nn=stack[a][0],mm=stack[a][1];
        if(map[nn-1][mm]==-2||map[nn][mm-1]==-2||map[nn+1][mm]==-2||map[nn][mm+1]==-2) {ans=map[nn][mm]+1;break;}
        if(map[nn-1][mm]==0)
          {
           map[nn-1][mm]=map[nn][mm]+1;
           top++;
           stack[top][0]=nn-1;stack[top][1]=mm;
          }
        if(map[nn][mm-1]==0)
          {
           map[nn][mm-1]=map[nn][mm]+1;
           top++;
           stack[top][0]=nn;stack[top][1]=mm-1;
          
          }
        if(map[nn+1][mm]==0)
          {
           map[nn+1][mm]=map[nn][mm]+1;
           top++;
           stack[top][0]=nn+1;stack[top][1]=mm;
          }
        if(map[nn][mm+1]==0)
          {
           map[nn][mm+1]=map[nn][mm]+1;
           top++;
           stack[top][0]=nn;stack[top][1]=mm+1;
          }   
       }
     if(ans==0) printf("= =\"\n");/*"出不來要多\特別注意這個該死的東西*/
     else printf("%d\n",ans); 
   }
 return 0;
}