头像

申侠




离线:9小时前


活动打卡代码 AcWing 178. 第K短路

申侠
18天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3302. 表达式求值

申侠
23天前
#include<bits/stdc++.h>
using namespace std;

stack<int> num;
stack<char> op;


void eval(){
    int d2 = num.top(); num.pop();
    int d1 = num.top(); num.pop();
    int o = op.top(); op.pop();
    if(o == '*') num.push(d1 * d2);
    else if(o == '/') num.push(d1 / d2);
    else if(o == '-') num.push(d1 - d2);
    else num.push(d1 + d2);
 }

int main(){
    unordered_map<char, int> m = {{'+', 0}, {'-', 0},{'*', 1},{'/', 1}};
    string ss;
    cin>>ss;
    for(int i=0;i< ss.size();i++){
        char q = ss[i];
        if(isdigit(q)){
            int j = i, s = 0;
            while(j < ss.size() && isdigit(ss[j])) s = s * 10 + ss[j++] - '0';
            num.push(s);
            i = j-1;
        }
        else if(q == '(') op.push(q);
        else if(q == ')'){
            while(op.top() != '(')  eval();
            op.pop();
        }
        else{
            while(op.size() && op.top() != '(' && m[op.top()] >= m[q])  eval();
            op.push(q);
        }
    }
    while(op.size()) eval();
    cout<<num.top();
 }


活动打卡代码 AcWing 1117. 单词接龙

申侠
24天前
#include<bits/stdc++.h>
using namespace std;

const int N = 21;
string s[N];
int g[N][N];
int cnt[N];
int ans;
int n;

void dfs(string dragon, int i){
    ans = max((int)dragon.size(), ans);
    cnt[i] --;
    for(int j=0; j<n;j++){
        if(g[i][j] && cnt[j]) dfs(dragon+s[j].substr(g[i][j]), j);
    }
    cnt[i] ++;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>s[i], cnt[i]=2;
    char start;
    cin>>start;
    for(int i=0;i<n;i++)
        for(int j=0; j<n;j++){
            string a = s[i], b = s[j];
            for(int k = 1; k < min((int)a.size(), (int)b.size());k++){
                if(a.substr(a.size()-k) == b.substr(0,k)){
                    g[i][j] = k;
                    break;
                }
            }
        }
    for(int i=0;i<n;i++){
        if(s[i][0] == start) dfs(s[i], i);
    }
    cout<<ans;
    return 0;
}





活动打卡代码 AcWing 1116. 马走日

申侠
24天前
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n,m,x,y;
int st[N][N];
int cnt;

void dfs(int x, int y, int k){
    if(k == n * m) {
        cnt ++; 
        return ;
    }
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1,2,2,1,-1,-2,-2,-1};
    for(int i=0;i<8;i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >=n || ny < 0 || ny >= m) continue;
        if(st[nx][ny]) continue;
        st[x][y] = true;
        dfs(nx,ny,k+1);
        st[x][y] = false;
    }

}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>x>>y;
        memset(st, false, sizeof st);
        cnt = 0;
        st[x][y] = true;
        dfs(x,y, 1);
        cout<<cnt<<endl;
    }
}


活动打卡代码 AcWing 1113. 红与黑

申侠
24天前
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
char g[N][N];
bool st[N][N];
int n,m;
int x, y;

int dfs(int x, int y){
    st[x][y]  = true;
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    int sum = 1;
    for(int i=0;i<4;i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if(st[nx][ny]) continue;
        if(g[nx][ny] == '#') continue;
        sum += dfs(nx, ny);
    }
    return sum;
}

int main(){
  while(cin>>m>>n, n||m){
      for(int i=0;i<n;i++) cin>>g[i];
      memset(st, false, sizeof st);
      for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j] == '@') x = i, y =j;
        cout<<dfs(x, y)<<endl;
  }
  return 0;
}


活动打卡代码 AcWing 1112. 迷宫

申侠
24天前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;

char g[N][N];
bool st[N][N];
int x1,y1,x2,y2;
int n;

// 5
// ...##
// ..#..
// ..##.
// .#.#.
// .#...
// 4 2 1 4


// 5
// ####.
// .#...
// .##..
// #..#.
// ###..
// 3 4 1 4

bool dfs(int x, int y){
    if(x==x2 && y == y2) return true;
    st[x][y] = true;
    // cout<<x<<" "<<y<<endl;
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    for(int i=0;i<4;i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= n || ny < 0 || ny >=n) continue;
        if(g[nx][ny] == '#') continue;
        if(st[nx][ny]) continue;
        if(dfs(nx,ny)) return true;
    }
    return false;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        memset(st, false, sizeof st);
        for(int i=0;i<n;i++) cin>>g[i];
        cin>>x1>>y1>>x2>>y2;
        if(g[x1][y1] == '#' || g[x2][y2] == '#'){
             puts("NO");
             continue;
        }
        if(dfs(x1,y1)) puts("YES");
        else puts("NO");
   }
   return 0;
}


活动打卡代码 AcWing 175. 电路维修

申侠
25天前
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
int d[N][N];
bool st[N][N];
char g[N][N];
int n, m;

int bfs(){
    deque<PII>  q;
    q.push_back({0, 0});
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);
    d[0][0] = 0;
    int dx[] = {-1,-1,1,1}, dy[] = {-1,1,1,-1};
    int ix[] = {-1,-1,0,0}, iy[] = {-1,0,0,-1};
    char s[] = "\\/\\/";

    while(q.size()){
        auto h = q.front();
        q.pop_front();
        int x = h.first, y = h.second;
        if(st[x][y]) continue;
        st[x][y] = true;

        for(int i=0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx > n || ny < 0 || ny > m) continue;
            int t = 0;
            if(g[x+ix[i]][y+iy[i]] != s[i]) t = 1;
            if(d[nx][ny] > d[x][y] + t){
                d[nx][ny] = d[x][y] + t;
                if(t) q.push_back({nx,ny});
                else q.push_front({nx,ny});

            }
        }
    }
    if(d[n][m] > 0x3f3f3f3f /2 )  return -1;
    else return d[n][m];
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++) scanf("%s", &g[i]);
        int ans = bfs();
        if(ans == -1) puts("NO SOLUTION");
        else cout<<ans<<endl;
    }
}



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

申侠
25天前
#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef pair<int ,int> PII;
const int N = 1010;
int g[N][N], d[N][N];
char c[N];

int main(){
    queue<PII> q;
    int n,m;
    cin>>n>>m;
    memset(d, 0x3f, sizeof d);
    for(int i=1;i<=n;i++){
        cin>>c+1;
        for(int j=1;j<=m;j++){
            g[i][j] = c[j]- '0';
            if(g[i][j]==1) q.push({i,j}), d[i][j] = 0;
        }        
    }
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    while(q.size()){
        auto head = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx = head.x + dx[i], ny = head.y + dy[i];
            if(nx <=n && nx >=1 &&  ny >=1 && ny <=m && g[nx][ny]==0 && d[nx][ny] > d[head.x][head.y] + 1)
                q.push({nx, ny}), d[nx][ny] = d[head.x][head.y] + 1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<d[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}


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

申侠
26天前
#include<bits/stdc++.h>
using namespace std;

const int N = 1000;
typedef pair<int, int> PII;
char g[N][N];
int d[N][N], st[N][N];
PII h[N*N];

int main(){
    int n, m;
    cin>>n>>m;
    int x1, y1, x2 ,y2;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            {
                cin>>g[i][j];
                if(g[i][j] == 'K') x1 = i, y1 = j;
                if(g[i][j] == 'H') x2 = i, y2 = j;
            }
    int hh=0, tt=0;
    // cout<<x2<<y2<<endl;
    h[0] = {x1, y1};
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    while(hh<=tt){
        auto head = h[hh++] ;
        int x = head.first, y = head.second;
        if(x == x2 && y == y2){
            cout<<d[x][y];
            break;
        }

        for(int i=0;i<8;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 1 && nx <=m && ny >=1 && ny <= n && !st[nx][ny] && g[nx][ny] != '*')  st[nx][ny] = 1, h[++tt] = {nx, ny}, d[nx][ny] = d[x][y] + 1;
        }
    }
    return 0;
}


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

申侠
26天前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int d[N], st[N];

int main(){
    int n,k;
    cin>>n>>k;
    queue<int> q;
    q.push(n);
    memset(d, -1, sizeof d);
    d[n] = 0;
    while(q.size()){
        int x = q.front();
        q.pop();
        if(x == k){
            cout<<d[x];
            break;
        }
        if(x -1 >= 0 && d[x-1]==-1) q.push(x-1), d[x-1] = d[x] + 1;
        if(x+1 <= N && d[x+1]==-1) q.push(x+1), d[x+1] = d[x] + 1;
        if(2*x <= N && d[2*x]==-1) q.push(2*x), d[2*x] = d[x] + 1;
    }
    return 0;
}