通用的基础算法要多多打磨两道搜索题目的解答过程

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

通用的基础算法要多多打磨两道搜索题目的解答过程

作者：

itdef , 2019-09-15 22:39:14 , 所有人可见 , 阅读 1299

7

2

题目是《算法问题实战策略》中的一题
oj地址是韩国网站连接比较慢 https://algospot.com/judge/problem/read/BOGGLE
大意如下

输入输出

输入
1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX

输出
PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES

估摸着很简单就蹭蹭8个方向DFS 代码写完
测试用例过了
代码如下

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n, m;
int record = 0;
const int dx[8] = { -1,-1,-1,1,1,1,0,0 };
const int dy[8] = { -1,0,1,-1,0,1,-1,1 };

bool isrange(int x, int y) {
    if (x < 0 || x >= 5 || y < 0 || y >= 5)
        return false;

    return true;
}



bool hasword(int x, int y, const string& word ,int idx,const vector<vector<char>>& table)
{
    if (!isrange(x, y)) return false;

    if (table[x][y] != word[idx]) return false;

    if (idx == word.size()-1) return true;

    for (int i = 0; i < 8; i++) {
        int nextx = x + dx[i];
        int nexty = y + dy[i];
        if (hasword(nextx, nexty, word,idx+1, table))
            return true;
    }

    return false;
}



int main()
{
    int t = 0;
    cin >> t;
    while (t--) {
        vector<vector<char>> table(5, vector<char>(5, 0));
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cin >> table[i][j];
            }
        }

        int check = 0;
        cin >> check;
        vector<string> checkWord;

        while (check--) {
            string s;
            cin >> s;
            int find = 0;
            record = 0;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (hasword(i, j, s, 0,table)) {
                        cout << s << " YES" << endl;
                        find = 1;
                        goto LABEL;
                    }
                }
            }

        LABEL:
            if (0 == find) {
                cout << s << " NO" << endl;
            }
        }
    }


    return 0;
}

但是居然一个特殊用例过不了代码被判为TLE

输入
1
AAAAA
AAAAA
AAAAA
AACCC
AACCB
1
AAAAAAAAAB

左思右想不得其门只得针对该例子进行了特殊处理翻转字符串！
添加代码不多仅仅多了 reverse(s.begin(), s.end()); 一行

#include <iostream>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;

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

vector<vector<int>> mem(5, vector<int>(5, 0));

bool isrange(int x, int y) {
    if (x < 0 || x >= 5 || y < 0 || y >= 5)
        return false;

    return true;
}



bool hasword(int x, int y, const string& word, int idx, const vector<vector<char>>& table)
{
    if (!isrange(x, y)) {
        return false;
    }

    if (table[x][y] != word[idx]) {

        return false;
    }

    if (idx >= word.size() - 1) return true;

    for (int i = 0; i < 8; i++) {
        int nextx = x + dx[i];
        int nexty = y + dy[i];
        if (hasword(nextx, nexty, word, idx + 1, table))
            return true;
    }

    return false;
}



int main()
{
    int t = 0;
    cin >> t;
    while (t--) {
        vector<vector<char>> table(5, vector<char>(5, 0));
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                cin >> table[i][j];
            }
        }

        int check = 0;
        cin >> check;
        vector<string> checkWord;

        while (check--) {
            string s;
            cin >> s;
            string copys = s;
            reverse(s.begin(), s.end());
            int find = 0;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    mem[i][j] = 1;
                }
            }
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (hasword(i, j, s, 0, table)) {
                        cout << copys << " YES" << endl;
                        find = 1;
                        goto LABEL;
                    }
                }
            }

        LABEL:
            if (0 == find) {
                cout << copys << " NO" << endl;
            }
        }
    }


    return 0;
}

但是实际上当测试字符串为AAAAAAAAABAAAAAAAA 也一样会TLE
所以实际上我们需要使用数组缓存从当前格子出发不能解决的字符串记录避免多次重复尝试失败的路径
代码添加了一个变量数组
int d[x][y][l]; 记录x y格子出发的尝试匹配长度为l的字符串能否成功，如果失败则置0。
下次DFS 发现该标记为 0 则直接返回不进行尝试

#include <bits/stdc++.h>
using namespace std;
int T,n,c[15][15],cw[15],len[15];
char a[15][15],w[15][15];
int nx[10] = {1,0,-1,-1,-1,0,1,1},ny[10] = {1,1,1,0,-1,-1,-1,0};
int dx,dy,is;
int d[15][15][15];

int dfs(int x,int y,int now,int l)
{
    if(d[x][y][l]) return 0;
    if(l == len[now]) return 1;
    d[x][y][l] = 1;
    is = 0;
    for(int i = 0;i < 8;i++)
    {
        dx = x+nx[i];
        dy = y+ny[i];
        if(a[dx][dy] == w[now][l])
        {
            if(dfs(dx,dy,now,l+1))
            {
                //c[x][y] = 0;
                return 1;
            }
        }
    }
    //d[x][y][l] = 0;
    return 0;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(cw,0,sizeof(cw));
        for(int i = 1;i <= 5;i++)
        {
            for(int j = 1;j <= 5;j++)
            {
                scanf(" %c",&a[i][j]);
            }
        }
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        {
            scanf("%s",w[i]);
            len[i] = strlen(w[i]);
            for(int j = 1;j <= 5;j++)
            {
                for(int k = 1;k <= 5;k++)
                {
                    if(a[j][k] == w[i][0])
                    {
                        if(dfs(j,k,i,1))
                        {
                            cw[i] = 1;
                            break;
                        }
                    }
                }
                if(cw[i]) break;
            }
            memset(d,0,sizeof(d));
        }
        for(int i = 1;i <= n;i++)
        {
            printf("%s %s\n",w[i],((cw[i] == 1) ? "YES" : "NO"));
        }
    }
}

//======================================================================================
下面是另一道搜索题目的解答过程
题目是《算法问题实战策略》中的一题
oj地址是韩国网站连接比较慢 https://algospot.com/judge/problem/read/PICNIC
大意如下

输入输出

输入
3 
2 1 
0 1 
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

输出
1
3
4

也是上来就撸一把DFS
全部能够匹配完成则计数增加1
但是有很多重复计算
我试过记录关系对的时候以数值大小为序只能排除一部分重复计算
错误的代码:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

/*
3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
//====================================
1
3
4
*/

int t;
int a, b;
int n, m;
typedef pair<int, int> PII;


bool isFriend(int i, int j, const vector<PII>& friendv)
{
    int minIdx = min(i, j);
    int maxIdx = max(i, j);

    for (auto& e : friendv) {
        if (e.first == minIdx && e.second == maxIdx)
            return true;
    }

    return false;
}


int dfs(bool isChecked[],const vector<PII>& friendv)
{
    int firstFree = -1;
    for (int i = 0; i < n; i++) {
        if (isChecked[i] == false){
            firstFree = i;
            break;
        }
    }

    if (-1 == firstFree)
        return 1;

    int ret = 0;


    for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
        if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false 
                && isFriend(firstFree, secondFree, friendv)) {
            isChecked[firstFree] = true; isChecked[secondFree] = true;
            ret += dfs(isChecked, friendv);
            isChecked[firstFree] = false; isChecked[secondFree] = false;
        }
    }


    return ret;
}




int main()
{
    cin >> t;

    while (t--) {
        cin >> n >> m;
        vector<PII> friendv;
        bool isChecked[160] = {false};
        while (m--) {
            cin >> a >> b;
            friendv.push_back({min(a,b),max(a,b)});
        }
        sort(friendv.begin(), friendv.end());
        cout << dfs(isChecked, friendv);
    }


    return 0;
}

经过调试发现DFS中双重循环有很大问题
i=0时候检测出 0 1配对然后检测出2 3 配对.
但是当i=2时也能检测2 3 配对以及 0 1 配对。

于是做了以下修改，解决重复问题
ac代码

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

/*
3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
//====================================
1
3
4
*/

int t;
int a, b;
int n, m;
typedef pair<int, int> PII;


bool isFriend(int i, int j, const vector<PII>& friendv)
{
    int minIdx = min(i, j);
    int maxIdx = max(i, j);

    for (auto& e : friendv) {
        if (e.first == minIdx && e.second == maxIdx)
            return true;
    }

    return false;
}


int dfs(bool isChecked[],const vector<PII>& friendv)
{
    int firstFree = -1;
    for (int i = 0; i < n; i++) {
        if (isChecked[i] == false){
            firstFree = i;
            break;
        }
    }

    if (-1 == firstFree)
        return 1;

    int ret = 0;


    for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
        if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false 
                && isFriend(firstFree, secondFree, friendv)) {
            isChecked[firstFree] = true; isChecked[secondFree] = true;
            ret += dfs(isChecked, friendv);
            isChecked[firstFree] = false; isChecked[secondFree] = false;
        }
    }


    return ret;
}




int main()
{
    cin >> t;

    while (t--) {
        cin >> n >> m;
        vector<PII> friendv;
        bool isChecked[160] = {false};
        while (m--) {
            cin >> a >> b;
            friendv.push_back({min(a,b),max(a,b)});
        }
        sort(friendv.begin(), friendv.end());
        cout << dfs(isChecked, friendv)<<endl;
    }


    return 0;
}

1 评论

itdef 2019-09-16 17:59

@yxc 大佬可否考虑把这些题目转移到acwing 么？可行么？
难度适中蛮适合新手练手
就是这韩国OJ网络连接太慢了

App 内打开

通用的基础算法 要多多打磨 两道搜索题目的解答过程

1 评论

通用的基础算法要多多打磨两道搜索题目的解答过程