# Week 10: DFS

###### tags: `S3 公開資源`

:::info
時間：04/23 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：DFS
直播連結：https://youtube.com/live/a116-co0tIo?feature=share
:::

# 必作題題解

[TOC]

## 三章_第一節

### [UVa 441 - Lotto](http://domen111.github.io/UVa-Easy-Viewer/?441)

撰寫者：fishhh

DFS 裸題，要特別注意的是輸出的地方要弄好
:::info
行末不能有空格
測資與測資間要空一行
最後一筆測資輸出完後 不輸出換行
:::
:::spoiler 參考程式碼

#include<iostream>
using namespace std;
int n,m,lott[100];
void dfs(int dep,bool ch[],int max){
	if(dep==6){
		int cnt = 0;
		for(int i=1;i<=m;i++){
			if(ch[i]){
				cout<<lott[i];
				cnt++;
				if(cnt!=6){
					cout<<" ";
				}
			}
		}
		cout<<"\n";
		return ;
	}
	for(int i=max+1;i<=m;i++){
		ch[i]=1;
		dfs(dep+1,ch,i);
		ch[i]=0;
	}
}
int main(){
	bool oup=1;
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	bool ed[100]={};
	while(cin>>m){
		if(m==0){
			return 0;
		}
		for(int i=1;i<=m;i++){
			cin>>lott[i];
		}
		if(!oup){
			cout<<"\n";
		}
		oup=0;
		dfs(0,ed,0);	
	}
}

:::

---

### [UVa 195 - Anagram](http://domen111.github.io/UVa-Easy-Viewer/?195)

撰寫者：fishhh

我覺得我自己的寫法不是很漂亮 但可以提供給你們看一下

作法：紀錄每個字元的數量，並且把它做類似hash的操作，讓他以題目的要求排列
再 DFS ， DFS的同時主要以最多開始拿，然後要避免跟上次拿一樣的(因為這樣就會造成重複排列)

要注意的是我裡面那個 preall 變數，代表的是如果要拿的前面還沒被拿完 那就從 1 開始拿 如果前面都拿完 那就從最多開始拿

我一開始沒寫 preall 結果會在這個 case 被卡掉
:::info
zzzzZ
:::

應該是要輸出
:::info
Zzzzz
zZzzz
zzZzz
...
:::

結果會變成
:::info
Zzzzz
zzzzZ
zzzZz
zzZzz
...
:::

:::spoiler

#include "iostream"
#include "vector"
using namespace std;
int cnt[100]={};
string s;
vector<pair<int,int>> now;
void dfs(int depth,int last_take){
	if(depth==s.size()){
		string ans = "";
		char add;
		for(auto i:now){
			if(i.second%2){
				add = ((i.second-1)/2+'A');
			}
			else{
				add =  ((i.second-2)/2+'a');
			}
			for(int k=0;k<i.first;k++){
				ans+=add;
			}
		}
		cout<<ans<<"\n";
		return ;
	}
	bool preall = 1;
	for(int i=1;i<=60;i++){
		if(cnt[i-1])preall = 0;
		if(i==last_take)continue;
		if(!preall){
			for(int j=1;j<=cnt[i];j++){
				now.push_back({j,i});
				cnt[i]-=j;
				dfs(depth+j,i);
				now.pop_back();
				cnt[i]+=j;
			}
		}
		else{
			for(int j=cnt[i];j>0;j--){
				now.push_back({j,i});
				cnt[i]-=j;
				dfs(depth+j,i);
				now.pop_back();
				cnt[i]+=j;
			}
		}
	}
	return ;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>s;
		for(int i=0;i<100;i++)cnt[i] = 0;
		for(char c:s){
			if(c>='A'&&c<='Z'){
				cnt[(c-'A'+1)*2-1]++;
			}
			else{
				cnt[(c-'a'+1)*2]++;
			}
			// [a,A,b,B,c,C.....]
		}
		dfs(0,8787);
	}
}

:::

---

### [ZJ e446 - 排列生成](https://zerojudge.tw/ShowProblem?problemid=e446)

撰寫者：Eason & 小麥:zap:

遞迴枚舉就好
記得最後把存在陣列的元素統一放到字串在輸出
不然會拿不到最後的 20%

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int n;
int arr[15];
bool is_in[15];

void solve(int cnt){
    if (cnt == n){
        string s;
        for (int i = 0; i < n; i++){
            // 這邊直接輸出 arr[i] 會 TLE
            if (arr[i] != 10) s += arr[i] + '0';
            else s += "10";
            s += ' ';
        }
        cout << s << '\n';
        return;
    }
    for (int i = 1; i <= n; i++){
        if (!is_in[i]){
            arr[cnt] = i;
            is_in[i] = true;
            solve (cnt + 1);
            is_in[i] = false;
        }
    }
    return;
}

int main(){
    weakson;
    cin >> n;
    for (int i = 1; i <= n; i++){
        arr[0] = i;
        is_in[i] = true;
        solve (1);
        is_in[i] = false;
    }
    return 0;
}

:::

<br>

:::spoiler 另解

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> numbers;

void solve() 
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        numbers.emplace_back(i);
    }

    string result = "";
    do
    {
        for (auto i : numbers) 
        {
            result += to_string(i) + ' ';
        }
        result += '\n';
    } while (next_permutation(numbers.begin(), numbers.end()));

    cout << result;
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

:::

---

### [TOJ 362 - D.大紙牌](https://toj.tfcis.org/oj/pro/362/)

撰寫者：Eason

直接暴力做就好
記得注意邊界

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

vector<int> s(18), h(18), d(18), c(18);
bool ans;

void solve(int sp, int hp, int dp, int cp){

    if (ans or (sp == 13 and hp == 13 and dp == 13 and cp == 13)){
        ans = true;
        return;
    }
    if (sp <= 12){
        if (hp <= 12 && s[sp] == h[hp]) solve (sp + 1, hp + 1, dp, cp);
        if (dp <= 12 && s[sp] == d[dp]) solve (sp + 1, hp, dp + 1, cp);
        if (cp <= 12 && s[sp] == c[cp]) solve (sp + 1, hp, dp, cp + 1);
    }
    if (hp <= 12){
        if (dp <= 12 && h[hp] == d[dp]) solve (sp, hp + 1, dp + 1, cp);
        if (cp <= 12 && h[hp] == c[cp]) solve (sp, hp + 1, dp, cp + 1);
    }
    if (dp <= 12){
        if (cp <= 12 && d[dp] == c[cp]) solve (sp, hp, dp + 1, cp + 1);
    }
    return;
}

int main(){
    weakson;

    for (int i = 0; i < 13; i++) cin >> s[i];
    for (int i = 0; i < 13; i++) cin >> h[i];
    for (int i = 0; i < 13; i++) cin >> d[i];
    for (int i = 0; i < 13; i++) cin >> c[i];

    solve (0, 0, 0, 0);

    if (ans) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

:::

---

### [TOJ 432 - Akechi 明智的選擇](https://toj.tfcis.org/oj/pro/432/)

撰寫者：Eason

用 DFS 解就好了

:::spoiler code

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int n, m;
int arr[1005][1005];
bool visited[1005][1005];

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

bool dfs(int x, int y){
    if (arr[x][y] == 1) return true;
    for (int i = 0; i < 4; i++){
        int rx = x + dx[i];
        int ry = y + dy[i];

        if (rx <= n && rx >= 1){
            if (ry <= m && ry >= 1){
                if (!visited[rx][ry]){
                    visited[rx][ry] = true;
                    if (dfs (rx, ry)){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    weakson;
    cin >> n >> m;

    int x, y;
    cin >> x >> y;
    arr[x][y] = 1;

    int u, v;
    cin >> u >> v;

    int f;
    cin >> f;
    for (int i = 0; i < f; i++){
        cin >> x >> y;
        visited[x][y] = 1;
    }

    if (dfs(u, v)) cout << "Cool!\n";
    else cout << "Harakiri!\n";

    return 0;
}

:::

---

### [33TOJ 487 - 停止爆炸](https://toj.tfcis.org/oj/pro/487/)

撰寫者：小麥

BFS水題

:::spoiler code

#include <bits/stdc++.h>

using namespace std;

struct Point
{
    int x;
    int y;
};

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
vector<vector<int>> world;
vector<vector<int>> visited;
queue<Point> bfs;
int n, m;
Point creeper;
Point player;

void solve() 
{
    cin >> n >> m;
    world.resize(n, vector<int>(m));
    visited.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> world[i][j];
        }
    }
    cin >> creeper.x >> creeper.y;
    cin >> player.x >> player.y;
    creeper.x -= 1;
    creeper.y -= 1;
    player.x -= 1;
    player.y -= 1;
    
    bfs.push(creeper);
    visited[creeper.x][creeper.y] = 1;
    while (bfs.size())
    {
        Point top = bfs.front();
        bfs.pop();

        int distance = abs(top.x - player.x) + abs(top.y - player.y);
        if (distance <= 3)
        {
            cout << "yes" << '\n';
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int x = top.x + dx[i];
            int y = top.y + dy[i];
            if (!(x >= 0 && x < n))
            {
                continue;
            }
            if (!(y >= 0 && y < m))
            {
                continue;   
            }
            Point next;
            next.x = x;
            next.y = y;
            int diff = world[next.x][next.y] - world[top.x][top.y];
            if (!(diff <= 1 && diff >= -2)) 
            {
                continue;
            }
            if (visited[next.x][next.y] == 1)
            {
                continue;
            }

            bfs.push(next);
            visited[next.x][next.y] = 1;
        }
    }

    cout << "no" << '\n';
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

:::

---