洛谷 P6207 [USACO06OCT] Cows on Skates G

題目傳送門：P6207Cows on Skates G

題目描述

本題使用 Special Judge，

Farmer John 把農場劃分為了一個 rr 行 cc 列的矩陣，并發現奶牛們無法通過其中一些區域，此刻，Bessie 位于坐標為 (1,1)(1,1) 的區域，并想到坐標為 (r,c)(r,c) 的牛棚享用晚餐，她知道，以她所在的區域為起點，每次移動至相鄰的四個區域之一，總有一些路徑可以到達牛棚，
這樣的路徑可能有無數種，請你輸出任意一種，并保證所需移動次數不超過 100000100000，

輸入格式

第一行兩個整數 r,c，
接下來 r 行，每行 c個字符，表示 Bessie 能否通過相應位置的區域，字符只可能是 . 或 *，

• . 表示 Bessie 可以通過該區域，
• * 表示 Bessie 無法通過該區域，

輸出格式

若干行，每行包含兩個用空格隔開的整數，表示 Bessie 依次通過的區域的坐標，

顯然，輸出的第一行是 1 1 ，最后一行是 r c，

相鄰的兩個坐標所表示的區域必須相鄰，

輸入輸出樣例

輸入 #1復制

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

輸出 #1復制

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8

說明/提示

【資料范圍】
對于 100% 的資料， 1≤r≤113，1≤c≤77，

*【樣例說明】 *

圖為樣例輸出的示意圖，答案不唯一，

分析：

這道迷宮題是一道典型的搜索題，因為這道題的資料范圍不大，所以我決定采用dfs來做這道題，
首先，總結一下dfs演算法，dfs（深度優先遍歷搜索）是搜索演算法的一種，它的遍歷程序如下：首先訪問指定的初始節點；若當前訪問的節點的鄰接節點有未被訪問的，則任選一個訪問；否則，退回到訪問過的最近的節點；直到與初始節點相通的全部頂點都訪問完畢；若此時圖中尚有節點（不與初始節點相通）未被訪問，則再選其中一個節點作為初始節點并訪問，然后重復上述程序； 否則，遍歷結束，

下面我們來看一幅圖模擬一下：

首先我們隨機選擇一個節點作為起始點（以V1作為起始點為例）

以V1作為起始點（標記），與V1相鄰的節點有V2，V3，隨機訪問其中一個，訪問V2（標記），然后V2有兩個節點 V4，V5，訪問V4（標記），V4有一個節點 V8，訪問V8（標記），V8有一個節點V5，訪問V5（標記），V5有一個節點V2，這時發現V2被標記過了，則從V5回溯到V8，V8只有一個節點且被標記，則從V8回溯到V4，從V4回溯到V2，從V2回溯到V1，這時發現V1有一個節點V3沒有標記，則訪問V3（標記），V3有兩個節點 V6 ,V7，訪問V6（標記），V6有一個節點V7，訪問V7（標記），遍歷結束，

訪問順序：V1->V2->V4->V8->V5->V3->V6->V7

附上dfs模板：

void dfs()
{
  if(到達目標狀態)
  {
    ...//根據題意輸出或者添加其他
    return ;
  }
  //根據題意使用
  /*if(越界或者非合法)
    return ;
  if(特殊狀態)//剪枝
    return ;*/
  else
  {
    for(根據題意擴展)//比如有4個方向，則回圈4次來搜索
    {
      進行修改操作;//根據題意進行修改
      if(判斷是否越界或者非法狀態)
      {
        修改操作;//根據題意是否添加
        標記;
        dfs();
        (還原標記即回溯)//根據題意看是否需要
      }
    }
  }
}

然后我們再來看這道題，我們從第一個點開始，判斷下一點是否滿足可走的條件（不越界或者處于合法狀態），如果可走，標記一下，然后繼續對這個點進行判斷，判斷它的下一個點是否滿足可走的條件，如果不滿足，則回溯到上一個點，
具體操作如下：
第一步，我們先輸入兩個數r，c，前者代表行數，后者代表每行字符的個數，然后每行依次輸入字符（字符只可能是 . 或 *），對每個字符，我們用bool陣列做一個標記，如果這個字符為 .,則標記為true，否則標記為false，

第二步，我們進行一些準備作業，定義一個結構體陣列（包含橫坐標和縱坐標），記錄點移動的路徑，然后用check()函式判斷點是否越界或者處于非法狀態（即是否被標記或者該點字符為*），從題目可知，點只能向四個方向移動（上，下，左，右），我們可以定義兩個陣列代表橫坐標和縱坐標（方向陣列）來對每個點的移動的方向進行修改，（即dfs模板中的擴展以及修改操作），然后定義一個變數sum記錄步數，

第三步，我們從(1,1)開始搜索，在dfs函式里，我們首先判斷該點是否到達目標點，如果滿足，則輸出并退出，否則，對該點根據方向陣列對周圍的點進行搜索，判斷它下一個點是否滿足check(), 如果滿足，對這個點進行標記，并且sum++, 否則回溯到上一個節點（即sum–)，繼續對上一個點進行搜索，然后再次判斷，直到找到目標點為止，

代碼：

#include<bits/stdc++.h>
using namespace std;
int r,c,sum=0;//sum記錄步數
bool used[200][200];
char g[200][200];
//定義一個結構體，代表走過的路徑
struct ss{
	int x,y;
};
ss arr[200];
int dx[5]={0,1,0,-1};//方向陣列
int dy[5]={1,0,-1,0};
inline bool check(int a,int b)//判斷是否越界及是否碰到障礙
{
	if(a<1||a>r||b<1||b>c||used[a][b]==false)
		return false;
	else
		return true;
}
//深搜
void dfs(int a,int b)
{
	//當走到最后一個點時，輸出
	if(a==r&&b==c)
	{
		for(int i=0;i<sum;i++)
			printf("%d %d\n",arr[i].x,arr[i].y);
		//exit(0);
		return ;
	}
	else
	{
		int tx,ty;
		for(int i=0;i<4;i++)
		{
			//對四個方向進行判斷
			tx=a+dx[i];
			ty=b+dy[i];
			if(check(tx,ty))
			{
				arr[sum].x=tx;
				arr[sum].y=ty;
				sum++;//記錄走過點的個數
				used[tx][ty]=false;//標記走過的點
				dfs(tx,ty);//找下一個點
				sum--;//回溯
			}
		}
	}
}
int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		scanf("%s",g[i]+1);
		for(int j=1;j<=c;j++)
		{
			if(g[i][j]=='*')//判斷是否為障礙，然后進行標記
				used[i][j]=false;
			else
				used[i][j]=true;
		}	
	}
	cout<<"1 1"<<endl;//不要忘記輸出1 1哦
	dfs(1,1);
	return 0;
}

結果：