技術文章 » 洛谷 P6207 [USACO06OCT] Cows on Skates G

洛谷 P6207 [USACO06OCT] Cows on Skates G

2020-10-26 13:00:45

洛谷 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。

*【樣例說明】 *

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

分析：

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

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

img

首先我們隨機選擇一個節點作為起始點（以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;
}

結果：

在這裡插入圖片描述