Тэмцээн #01

Өнгөрөсөн амралтын өдрүүдэд зохиогдсон https://www.hackerrank.com/contests/sict01/challenges тэмцээнд идэвхитэй оролцож амжилт гаргасан найзууддаа баярлалаа.

Шат, Чапаев Петка 2 бодлогуудын хувьд шийдэл нь тодорхой хялбар бодлого тул бодолт хийлгүй орхиё.



Индиан Жонс ба Нууцлаг хаалга бодлогын шийдэл нь орж хоёр хүснэгтийг тулгаж үзэх замаар хоёр дахь хүснэгт эхний хүснэгтэд агуулагдаж байгаа эсэхийг шалгахад хангалттай.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int R, C, r, c, i, j, t;
    short grid[1000][1000], pattern[1000][1000];
    //Accepting Inputs
    cin>>t;
    while (t--) {
    cin>>R>>C;
    for(i=0; i<R; i++) {
        for(j=0; j<C; j++){
            char c;
            cin>>c;
            grid[i][j] = c - '0';
        }
    } 
    cin>>r>>c;
    for(i=0; i<r; i++) {
        for(j=0; j<c; j++){
            char c;
            cin>>c;
            pattern[i][j] = c - '0';
        }
    }
    //Searching grid
    bool flag = false;
    for(i=0; i<=R-r; i++){
        for(j=0; j<=C-c; j++) {
            if(grid[i][j]==pattern[0][0]){
                int a, b;
                //cout<<i<<" "<<j<<" "<<grid[i][j]<<endl;
                for(a=0; a<r; a++){
                    for (b=0; b<c; b++){
                        if(grid[i+a][j+b] == pattern[a][b]) flag = true;
                        else {
                            flag = false;
                            break;
                        }
                    }
                    if(!flag) break;
                }
            }
            if(flag) {
                cout<<"YES"<<endl;
                break;
            }
        }
        if(flag) break;
      }
        if(!flag) cout<<"NO"<<endl;
    }
    return 0;
}

Түвшний нэвтрэлт бодлогын хувьд өгөгдсөн S цэгээс графын бүх оройд түвшний нэвтрэлт хийхдээ тухайн оройд хэдэн алхамаар очсоныг(нэг алхам нь 6 урттай) нэг массивт тэмдэглээд, тухайн массивийн агуулгыг хэвлэхэд хангалттай.

#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

vector< vector<int> >g(1001);
list< int >nodes;
map<int, bool>v;
bool visited[1001];
int steps[1001];
void bfs(){
    int s = nodes.front();
    nodes.pop_front();
    for(int i = 0; i < g[s].size(); i++){
        if(!visited[g[s][i]]){
            steps[g[s][i]] = steps[s] + 6;           
            nodes.push_back(g[s][i]);
            visited[g[s][i]] = true;
        }
    }
    
    if(nodes.size()){    
        bfs();
    }
}

int main() {
    int t, m, n, x, y, s;
    
    scanf("%d", &t);
    while(t--){
        
        nodes.clear();
        
        for(int i = 0; i < 1001; i++){ visited[i] = false; steps[i] = -1; g[i].clear(); }
        
        scanf("%d %d", &n, &m);
        
        for(int i = 0; i < m; i++){
            scanf("%d%d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        scanf("%d", &s);
        nodes.push_back(s);
        steps[s] = 0;
        bfs();
        
          for(int i = 1; i <= n; i++){
              if(i != s)    
                printf("%d ", steps[i]);
          }
        printf("\n");
    }
    return 0;
}

Хүснэгт эргүүлэлт бодлогын хувьд өгөгдсөн хүснэгт

a11  a12  a13  a14  a15

a21  a22  a23  a24  a25

a31  a32  a33  a34  a35

a41  a42  a43  a44  a45

гэж бодвол

Гадна хүрээг:

a11  a12  a13  a14  a15

a21                 a25

a31                 a35

a41  a42  a43  a44  a45

->

a11 <- a12 <- a13 <- a14 <- a15 <- a25 <- a35 <- a45 <- a44 <- a43 <- a42 <- a41 <- a31 <- a21

Түүний дотор хүрээг:

    a22  a23  a24

    a32  a33  a34

->

a22 <- a23 <- a24 <- a34 <- a33 <- a32

гэсэн цуваанд шилжүүллээ гэс бодоход R удаагийн эргүүлэлтийн дараах тухайн элементийн байршил АгуулагдажбайгааЦуваа[R%(цувааны урт)] гэсэн байдлаар олдоно.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;


void printMatrix(vector< vector<int> > & matrix, int M, int N)
{

    for(int row = 0; row < M; row++)
    {
        for(int column = 0; column < N; column++)
        {
            printf("%d ", matrix[row][column]);
        }
        printf("\n");
    }

}

void Matrix_Rotation(vector< vector<int> > & matrix, int M, int N, int R)
{
    vector< vector<int> > old_matrix = matrix;
  
    int num_rings = min(M,N)/2;
    int num_elems_to_queue;
    for(int ring = 0; ring < num_rings; ring++)
    {
        queue<int> ring_queue;
     //populate ring queue
     
     //populate top side
     num_elems_to_queue = (N - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            ring_queue.push(matrix[ring][ring + num_elems_queued]);
        }

     //populate right side
     num_elems_to_queue = (M - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            ring_queue.push(matrix[ring + num_elems_queued][N - 1 - ring]);
        }

        //populate bottom side
     num_elems_to_queue = (N - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            ring_queue.push(matrix[M - 1 - ring][N - 1 - ring - num_elems_queued]);
        }

        //populate left side
     num_elems_to_queue = (M - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            ring_queue.push(matrix[M - 1 - ring - num_elems_queued][ring]);
        }

        int rotations = R % ring_queue.size();
        for(int r = 0; r < rotations; r++)
        {
            ring_queue.push(ring_queue.front());
            ring_queue.pop();
        }
        
        //populate top side
     num_elems_to_queue = (N - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            matrix[ring][ring + num_elems_queued] = ring_queue.front();
            ring_queue.pop();
        }

     //populate right side
     num_elems_to_queue = (M - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            matrix[ring + num_elems_queued][N - 1 - ring] = ring_queue.front();
            ring_queue.pop();
        }

        //populate bottom side
     num_elems_to_queue = (N - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            matrix[M - 1 - ring][N - 1 - ring - num_elems_queued] = ring_queue.front();
            ring_queue.pop();
        }

        //populate left side
     num_elems_to_queue = (M - (2 * ring)) - 1;
        for(int num_elems_queued = 0; num_elems_queued < num_elems_to_queue; num_elems_queued++)
        {
            matrix[M - 1 - ring - num_elems_queued][ring] = ring_queue.front();
            ring_queue.pop();
        }

        
    }

    printMatrix(matrix, M, N);
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int M, N, R, elem;
    cin >> M;
    cin >> N;
    cin >> R;

    vector< vector< int > > matrix;
    vector< int > row_vec;
    for(int row = 0; row < M; row++)
    {
        for(int column = 0; column < N; column++)
        {
            cin >> elem;
            row_vec.push_back(elem);
        }
        matrix.push_back(row_vec);
        row_vec.clear();
    }

    Matrix_Rotation(matrix, M, N, R);
    return 0;
}