头像

Ker


访客:2968

离线:7分钟前


活动打卡代码 AcWing 1107. 魔板

Ker
7小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;


void set(string state)
{
    for(int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for(int i = 7, j = 0; j < 4; i -- , j ++ ) g[1][j] = state[i];
}
string get()
{
    string res;

    for(int i = 0; i < 4; i ++ ) res += g[0][i];
    for(int i = 3; i >= 0; i -- ) res += g[1][i];
    return res;
}
string move0(string state)
{
    set(state);
    for(int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);

    return get();
}
string move1(string state)
{
     set(state);
     int v0 = g[0][3], v1 = g[1][3];
     for(int i = 3; i >= 0; i -- )
     {
         g[0][i] = g[0][i - 1];
         g[1][i] = g[1][i - 1];
     }
     g[0][0] = v0, g[1][0] = v1;
     return get();
}
string move2(string state)
{
    set(state);

    int v = g[0][1];

    g[0][1] = g[1][1];

    g[1][1] = g[1][2];

    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}

int bfs(string start, string end)
{
    if(start == end) return 0;

    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();

        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for(int i = 0; i < 3; i ++ )
            if(!dist.count(m[i])) 
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i, t};
                q.push(m[i]);
                if(m[i] == end) return dist[end];
            }
    }
    return -1;
}

int main()
{
    int x;
    string start, end;
    for(int i = 0; i < 8 ; i ++ )
    {
        cin >> x;
        end += char(x + '0');
    }

    for(int i = 0; i < 8; i ++ ) start += (i + '1');

    int step = bfs(start, end);

    cout << step << endl;

    string res;
    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if(step > 0) cout << res << endl;

    return 0;

}


新鲜事 原文

Ker
10小时前
不能再三天打鱼两天晒网了,肝!!!


活动打卡代码 AcWing 173. 矩阵距离

Ker
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;

const int N = 1010, M = N * N;
int n, m;
int dist[N][N];
PII q[M];
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs()
{
    memset(dist, -1, sizeof dist);
    int hh = 0, tt = -1;

    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ ) 
            if(g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[++tt] = {i, j};
            }

    while(hh <= tt)
    {
        PII t = q[ hh ++ ];
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];

            if( a < 0 || a >= n || b < 0 || b >= m) continue;
            if(dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a,b};
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i< n; i ++ ) scanf("%s", &g[i]);

    bfs();

    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < m; j ++ )
            printf("%d ",dist[i][j]);
        puts("");
    }

    return 0;
}



活动打卡代码 AcWing 1100. 抓住那头牛

Ker
8天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 +  10;
int n, k;
int q[N];
int dist[N];
int bfs()
{
    memset(dist, -1,sizeof dist);
    dist[n] = 0;
    q[0] = n;

    int hh = 0, tt = 0;
    while(hh <= tt)
    {
        int t = q[ hh ++ ];

        if(t == k) return dist[k];
        if(t + 1 < N && dist[t + 1] == -1)
        {
            dist[t + 1] = dist[t] + 1;
            q[++tt] = t + 1;
        }
        if(t - 1 >= 0 && dist[t - 1] == -1)
        {
            dist[t - 1] = dist[t] + 1;
            q[ ++ tt] = t - 1;
        }
        if(t * 2 < N && dist[t * 2] == -1)
        {
            dist[t * 2] = dist[t] + 1;
            q[ ++ tt] = t * 2;
        }
    }
    return -1;
}
int main()
{
    cin >> n >> k;
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 188. 武士风度的牛

Ker
8天前
#include <cstring>
#include <algorithm>
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 155, M = N * N;
int n, m;
char g[N][N];
PII q[M];
int dist[N][N];
int bfs()
{
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

    int sx, sy;
    for(int i = 0 ; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            if(g[i][j] == 'K')
                sx =  i, sy = j;

    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    memset(dist, -1, sizeof dist);
    dist[sx][sy] = 0;

    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        for(int i = 0; i < 8; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '*') continue;
            if(dist[a][b] != -1) continue;
            if(g[a][b] == 'H') return dist[t.x][t.y] + 1;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a, b};
        }
    }
    return -1;
}
int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i ++ ) cin >> g[i];
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 1076. 迷宫问题

Ker
8天前
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int g[N][N];
PII q[M];
PII pre[N][N];
void bfs(int sx,int sy)
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0 ,-1};
    int hh = 0, tt = 0;
    q[0] = {sx,sy};
    memset(pre, - 1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(g[a][b]) continue;
            if(pre[a][b].x != -1) continue;

            q[++ tt] = {a,b};
            pre[a][b] = t;

        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n ; i ++ )
        for(int j = 0; j < n; j ++ )
            scanf("%d", &g[i][j]);

    bfs(n - 1, n - 1);
    PII end(0, 0);

    while(true)
    {
        printf("%d %d\n", end.x, end.y);

        if(end.x == n - 1 && end.y == n - 1) break;
        end = pre[end.x][end.y];
    }
    return 0;
}


活动打卡代码 AcWing 1106. 山峰和山谷

Ker
10天前
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;
int n;
int h[N][N];
bool st[N][N];
PII q[M];
void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        for(int i = t.x - 1; i <= t.x + 1; i ++ )
            for(int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if(i == t.x && j == t.y) continue;
                if(i < 0 || i >= n || j < 0 || j >= n) continue;
                if(h[i][j] != h[t.x][t.y])
                {
                    if(h[i][j] > h[t.x][t.y]) has_higher = true;
                    else has_lower = true;
                }
                else if (!st[i][j]) 
                {
                    q[ ++ tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n;i ++ )
        for(int j = 0; j < n; j ++ )
            scanf("%d",&h[i][j]);

    int peak = 0, valley = 0;
    for(int i = 0 ;i < n ; i ++)
        for(int j = 0; j < n; j ++ )
            if(!st[i][j])
            {
                bool has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if(!has_higher) peak ++;
                if(!has_lower) valley ++;

            }

    printf("%d %d\n", peak, valley);
    return 0;
}



活动打卡代码 AcWing 1098. 城堡问题

Ker
10天前
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;

int n, m;
PII q[M];
int g[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
bool st[N][N];
int bfs(int sx, int sy)
{
    int hh = 0, tt = 0;

    q[0] = {sx, sy};

    st[sx][sy] = true;

    int area = 0;

    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        area ++;
        for(int i = 0; i < 4; i ++ ) 
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[a][b]) continue;
            if(g[t.x][t.y] >> i & 1) continue;


            q[++ tt] = {a, b};
            st[a][b] = true;
        }

    }
    return area;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            cin >> g[i][j];


    int cnt = 0 , area = 0;    
    for (int i = 0; i < n ; i ++ ) 
        for(int j = 0; j < m; j ++ )
        if(!st[i][j])
        {
            area = max(area, bfs(i, j));
            cnt ++ ;
        }
    cout << cnt << endl;
    cout << area << endl;

    return 0;
}



活动打卡代码 AcWing 1097. 池塘计数

Ker
10天前
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;


const int N = 1010, M = N * N;
int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0 ;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while(hh <= tt)
    {
        PII t = q[hh ++ ];

        for(int i = t.x - 1; i <= t.x + 1; i ++ )
            for(int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if(i == t.x && j == t.y) continue;
                if(i < 0 || i >= n || j < 0 || j >= m) continue;
                if(g[i][j] == '.' || st[i][j]) continue;

                q[++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}
int main()
{
    scanf("%d %d",&n, &m);
    for(int i = 0; i < n ; i ++ ) scanf("%s", &g[i]);

    int cnt = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            if(g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++;
            }
    printf("%d\n",cnt);
}




Ker
30天前

解题思路

做法:使用指针i, j分别指向首尾,如果h[i] > h[j]则j – , 否则 i ++ ,直到i = j 为止,此时移动i或j都是可以的,每次迭代更新最大值(通过最短的水柱所形成的i -> j 所围成的面积来更新)。

复杂度分析:双指针共扫描n次, 总复杂度O(n);

代码

class Solution {
public:
    int maxArea(vector<int>& height) {
         int res = 0;
         for(int i = 0, j = height.size() - 1; i < j; )
         {
             res = max(res, min(height[i], height[j]) * (j - i));
             if(height[i] > height[j]) j --;
             else i ++ ;
         }
         return res;
    }
};