头像

AAAL




离线:9分钟前


最近来访(28)
用户头像
xiaohu
用户头像
snut_lmz
用户头像
jaylenwanghitsz
用户头像
火球大的脸盆
用户头像
codewt
用户头像
记着别人的好
用户头像
北海没有WA
用户头像
呐呐呐呐
用户头像
阿骨打
用户头像
slight
用户头像
Chuckie
用户头像
V1CI-_-
用户头像
哄哄_20
用户头像
yushulinfeng
用户头像
hutos
用户头像
HDB
用户头像
文刀
用户头像
LightQuantum
用户头像
Yeahhh
用户头像
zqc


AAAL
2小时前

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = N * N;

int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    deque<PII> q;
    q.push_back({0, 0});

    char cs[] = "/\\/\\";//按我的想法也成了!!!!
    int dx[4] = {1, -1, -1, 1}, dy[4] = {-1, -1, 1, 1};
    int ix[4] = {0, -1, -1, 0}, iy[4] = {-1, -1, 0, 0};

    while (q.size())
    {
        PII t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        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;

            int ca = t.x + ix[i], cb = t.y + iy[i];
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);

            if (d <= dist[a][b])
            {
                dist[a][b] = d;

                if (g[ca][cb] != cs[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }

    return dist[n][m];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

        int t = bfs();
        if ((m + n) % 2) puts("NO SOLUTION");
        else printf("%d\n", t);
    }

    return 0;
}


理解ix和dx数组图
80572396141690839.jpg




AAAL
12小时前

注意这种处理输入输出的方式,和大代码量题的练习

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
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 = 1; i <= 8; i ++ )//!!!
    start += char('0' + i);

    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;
}




AAAL
15小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int dist[N][N];
int n,m;
queue<PII> q;
char a[N][N];

void bfs(){
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ){
            if(a[i][j] == '1'){
                q.push({i , j});
                dist[i][j] = 0;
            }
        }
    while(q.size()){
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++ ){
            int x = t.x + dx[i] , y = t.y + dy[i];
            if(dist[x][y] != -1) continue;
            if(x < 0 || y < 0 || x >= n || y >= m) continue;

            dist[x][y] = dist[t.x][t.y] + 1;
            q.push({x , y});
        }

    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )//输入相邻之间没有空格所以用char读入用int会错
        cin >> a[i];
    bfs();

    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            cout << dist[i][j]<<' ';
        }
        cout <<endl;
    }

}



AAAL
1天前

不能用st数组存是否遍历再用res++记录步数
这样算的是总尝试数每步会加八次肯定错

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 200;
char g[N][N];
int dist[N][N];
queue<PII> q;
int r, c;

int  bfs(int sx , int sy){
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    memset(dist, -1, sizeof dist);
    dist[sx][sy] = 0;
    q.push({sx ,sy});

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

        for (int i = 0; i < 8 ; i ++ ){
            int x1 = t.x + dx[i], y1 = t.y + dy[i];
            if(x1 < 0 || x1 >= c || y1 < 0 || y1 >= r) continue;
            if(g[x1][y1] == '*') continue;
            if(dist[x1][y1] != -1) continue;
            if(g[x1][y1] == 'H' ) {
                return dist[t.x][t.y] + 1;
            }
            dist[x1][y1] = dist[t.x][t.y] + 1;
            q.push({x1, y1});
        }
    }
    return -1;

}

int main()
{
    cin >> r >> c;
    for (int i = 0; i < c; i ++ )
        cin >> g[i];

    int x , y;
    for (int i = 0; i < c; i ++ )
        for (int j = 0; j < r; j ++ ){
            if(g[i][j] == 'K'){
                x = i;
                y = j;
                break;
            }
        }
    cout << bfs(x , y);
    return 0;
}




AAAL
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 200010;
int n,k;
int dist[N];
queue<int> q;

int bfs(){

    memset(dist, -1, sizeof dist);
    dist[n] = 0;
    q.push(n);

    while(q.size()){
        int t = q.front();
        q.pop();
        if(t == k) {
            return dist[k];
        }
        if(t + 1 < N && dist[t + 1] == -1) {
            dist[t + 1] = dist[t] + 1;
            q.push(t + 1);
        }
        if( t - 1 >= 0  && dist[t - 1] == -1) {
            dist[t - 1] = dist[t] + 1;
            q.push(t - 1);
        }
        if(t * 2 < N && dist[t * 2] == -1){
            dist[t * 2] = dist[t] + 1;
            q.push(t * 2);
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;
    cout << bfs();
    return 0;
}



AAAL
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#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];
queue<PII> q;
PII pre[N][N];
bool st[N][N];
void bfs(int sx, int sy){
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    q.push({sx, sy});
    st[sx][sy] = true;
    while(q.size()){
        PII t = q.front();
        q.pop();

        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(st[a][b]) continue;

            q.push({a, b});
            pre[a][b] = t;
            st[a][b] = true;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> g[i][j];
    bfs(n - 1, n - 1);//终点往起点(0 , 0)遍历,记录每次的出发点
    PII previous(0 ,0);

    while(true){
        printf("%d %d\n", previous.x, previous.y);//(0,0)开始遍历到n - 1,就是从开始到终点的路径
        if(previous.x == n - 1 &&previous.y == n - 1) break;
        previous = pre[previous.x][previous.y];
    }

    return 0;
} 



AAAL
2天前

bfs 注意题意是淹了多少个岛,不是还有多少个#字符

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second


using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
int n;
int res =0;

bool bfs(int sx , int sy){
    int sum = 0;
    bool mark;
    queue<PII> q;
    q.push({sx,sy});

    while(q.size()){
        auto t = q.front();
        q.pop();
        mark = 1;
        for (int i = 0; i < 4; i ++ ){
            int x1 = t.x + dx[i], y1 = t.y + dy[i];
            if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= n) continue;
            if(g[x1][y1] == '.') {mark = 0; continue;}
            if(st[x1][y1]) continue;

            st[x1][y1] = true;
            q.push({x1,y1});
        }

        if(mark == 1) sum+=1;
    }

    if(sum) return 1;

    else return 0;
}

int main()
{
    cin >> n;
    int allisland = 0,lifeisland = 0;
    for (int i = 0; i < n; i ++ )
    cin >> g[i];
    for (int i = 0; i < n; i ++ )
        for(int j = 0;j < n;j++)
        {
            if(g[i][j] == '#' && !st[i][j]){
            allisland++;
            lifeisland += bfs(i ,j);
            }
        }
    cout << allisland -  lifeisland;

    return 0;
}


活动打卡代码 AcWing 1695. 果壳游戏

AAAL
2天前

模拟

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int main()
{
    cin >> n;
    int p[4] = {0,1,2,3};//p[i]表示 i位置存的是几号
    int res[4] = {0};//res表示开始是位于哪个坚果壳下猜对的答案数

    for (int i = 1; i <= n; i ++ )
    {
        int a,b,g;
        cin >> a>> b >> g;
        swap(p[a] ,p[b]);
        res[p[g]]++;
    }
    cout << max({res[1],res[2],res[3]});


    return 0;
}


活动打卡代码 AcWing 1714. 混合牛奶

AAAL
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int c1,c2,c3,v1,v2,v3;

int main()
{
    cin >> v1>> c1>> v2 >> c2 >> v3 >>c3;
    for (int i = 1; i <= 100; i ++ ){
            int t = i % 3;
            if(t == 1){
                int c = min(c1 , v2 - c2);//注意核心:计算每次倒多少牛奶 ,再在一瓶加上,另一瓶减去,不要直接算容量会死循环;
                c1 = c1 - c;
                c2 = c2 + c;
            }
            if(t == 2){
                int c = min(c2 , v3 - c3);
                c2 = c2 - c;
                c3 = c3 + c;
            }
            if(t == 0){//对三取模哪有得三的!!!!
                int c = min(c3 , v1 - c1);
                c3 = c3 - c;
                c1 = c1 + c;
            }
        }

    cout<< c1 <<endl<< c2<<endl<<c3;
    return 0;
}


活动打卡代码 AcWing 1659. 社交距离 I

AAAL
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n,m;
char str[N];
int p[N];
int main()
{
    scanf("%d%s", &n, str + 1);
    for (int i = 1; i <= n; i ++ )
        if (str[i] == '1')
            p[ ++ m] = i;

    if (!m) cout << n-1;
    else{
        int xmin = N;
        for (int i = 1; i < m; i ++ ){
            xmin = min(xmin , p[i+1] - p[i]);
        }

        int y = max((p[1] - 1) / 2 , (n - p[m]) / 2);
        for (int i = 1; i < m; i ++ )
            y = max((p[i + 1] - p[i]) / 3 , y);

        int y1 = p[1] - 1, y2 = n -p[m];
        if(y1 < y2 ) swap(y1 , y2); // y1是最大值,y2是次最大值
        for (int i = 1; i < m; i ++ ){
            int d = (p[i + 1] -p[i]) / 2;
            if(d >= y1) y2 = y1 ,y1 = d;
            else if(d > y2) y2 = d;
        }
        cout << min(xmin, max(y , y2));

    }
    return 0;
}