(step 4.3.5)hdu 1035(Robot Motion——DFS)

題目大意:輸入三個整數n，m，k，分別表示在接下來有一個n行m列的地圖。一個機器人從第一行的第k列進入。問機器人經過多少步才能出來。如果出現了循環

則輸出循環的步數

解題思路:DFS

代碼如下(有詳細的解釋):

 * 1035_1.cpp 
 * 
 *  Created on: 2013年8月17日 
 *      Author: Administrator 
 */  
/*簡單搜索題，看注釋： 
*/  
#include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<string>   
#include<cmath>   
#include<algorithm>   
using namespace std;  
  
/** 
 * map[][] :用來標記地圖 
 * num[x][y] : 用來標記走到(x,y)這個點的時候用了多少步. 
 * 如果num[x][y] == 0,則證明這一步還沒走過。否則,根據題意則可能出現了循環 
 * 
 * n: 行數 
 * m: 列數 
 * k: 從第一行的第k列進入地圖 
 * t: 總共走了多少步 
 * lop: 循環的步數 
 */  
char map[11][11];  
int num[11][11];  
int n, m, k, lop, t;  
  
/** 
 * 判斷是否越界 
 */  
bool Overmap(int x, int y) {  
    if (x < 1 || x > n || y < 1 || y > m) {  
        return true;  
    } else {  
        return false;  
    }  
}  
  
void Dfs(int x, int y) {  
    //如果越界了或者是出現了循環   
    if (Overmap(x, y) || lop > 0) {  
           if (lop > 0) {  
            printf("%d step(s) before a loop of %d step(s)\n", t - lop, lop);  
        } else {  
            printf("%d step(s) to exit\n", t);  
        }  
        return ;  
    }  
  
  
    if (num[x][y] == 0) {//如果這一步還沒有走過   
        num[x][y] = ++t;  
    } else {//判斷是否有循環(如果這一步已經走過,則計算循環的步數)   
        lop = t - num[x][y] + 1;  
    }//else   
  
    //遍歷狀態   
    switch(map[x][y]) {  
        case 'N': x--; Dfs(x, y); x++; break; //Dfs最主要：前加的條件，在之後要返回   
        case 'E': y++; Dfs(x, y); y--; break;  
        case 'S': x++; Dfs(x, y); x--; break;  
        case 'W': y--; Dfs(x, y); y++; break;  
    }//switch   
}//dfs   
  
  
int main() {  
    while (scanf("%d %d %d", &n, &m, &k) != EOF, n) {  
        memset(map, 0, sizeof(map));  
        memset(num, 0, sizeof(num));  
  
        lop = 0;  
        t = 0;  
        getchar();  
        for (int i = 1; i <= n; i++) {  
            scanf("%s", map[i] + 1);  
            getchar();  
        }  
        Dfs(1, k);  
  
    }  
}  

/*
 * 1035_1.cpp
 *
 *  Created on: 2013年8月17日
 *      Author: Administrator
 */
/*簡單搜索題，看注釋：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

/**
 * map[][] :用來標記地圖
 * num[x][y] : 用來標記走到(x,y)這個點的時候用了多少步.
 * 如果num[x][y] == 0,則證明這一步還沒走過。否則,根據題意則可能出現了循環
 *
 * n: 行數
 * m: 列數
 * k: 從第一行的第k列進入地圖
 * t: 總共走了多少步
 * lop: 循環的步數
 */
char map[11][11];
int num[11][11];
int n, m, k, lop, t;

/**
 * 判斷是否越界
 */
bool Overmap(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) {
        return true;
    } else {
        return false;
    }
}

void Dfs(int x, int y) {
	//如果越界了或者是出現了循環
    if (Overmap(x, y) || lop > 0) {
           if (lop > 0) {
            printf("%d step(s) before a loop of %d step(s)\n", t - lop, lop);
        } else {
            printf("%d step(s) to exit\n", t);
        }
        return ;
    }


    if (num[x][y] == 0) {//如果這一步還沒有走過
        num[x][y] = ++t;
    } else {//判斷是否有循環(如果這一步已經走過,則計算循環的步數)
        lop = t - num[x][y] + 1;
    }//else

    //遍歷狀態
    switch(map[x][y]) {
        case 'N': x--; Dfs(x, y); x++; break; //Dfs最主要：前加的條件，在之後要返回
        case 'E': y++; Dfs(x, y); y--; break;
        case 'S': x++; Dfs(x, y); x--; break;
        case 'W': y--; Dfs(x, y); y++; break;
    }//switch
}//dfs


int main() {
	while (scanf("%d %d %d", &n, &m, &k) != EOF, n) {
        memset(map, 0, sizeof(map));
        memset(num, 0, sizeof(num));

        lop = 0;
        t = 0;
        getchar();
        for (int i = 1; i <= n; i++) {
            scanf("%s", map[i] + 1);
            getchar();
        }
        Dfs(1, k);

    }
}