C++

Forum

 
Testing

May 6, 2019 at 8:34pm
jmpt (13)
If you can see this, please tell me. I seem to not be able to write!!!
May 6, 2019 at 8:35pm
jmpt (13)
Nevermind. Preview seems not to work. Please ignore.
May 7, 2019 at 6:07pm
deleted account xyzzy (5768)
With new topic posts none of the functions, format and preview, work.

Save the opening post, then add or edit the post and they will.

This is a problem that has been known for a long time. The admin has been contacted about it many times before. So far nothing has been done to fix it.
Last edited on May 7, 2019 at 6:07pm
Jun 21, 2019 at 12:25pm
epdlqlemqpzja1234 (2)
Test Group
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include<iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

int MIN = 10000;
int Y;
int X;
int mine[100+10][100+10];
vector<pair<int, int>> adj[100+10][100+10];

int bfs(int y, int x)
{
    queue<pair<int, int>> que; 
    int visited[100+10][100+10]={0,};

    que.push(make_pair(y,x));
    visited[y][x] = 1;
    
    while(!que.empty()){
        pair<int,int> v = que.front();
        que.pop();
        
        if(v.first == Y && v.second == X){
            if(MIN > visited[v.first][v.second]){
                MIN = visited[v.first][v.second];
            }
        }

        for(size_t i=0; i<adj[v.first][v.second].size(); ++i){
            if(visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] == 0)
                que.push(make_pair(adj[v.first][v.second][i].first, adj[v.first][v.second][i].second));
                visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] = visited[v.first][v.second]+1;
                
        }
    }

    // for(int y=1; y<=Y; ++y){
    //     for(int x=1; x<=X; ++x){
    //         printf("%d ", visited[y][x]);
    //     }
    //     printf("\n");
    // }

    return MIN;
}

int main()
{
    scanf("%d %d", &Y, &X);
    for(int y=1; y<=Y ; ++y){
        for(int x=1; x<=X; ++x){
            scanf("%1d", &mine[y][x]);
        }
    }

    //make adjacent list
    for(int y=1; y<=Y; ++y){
        for(int x=1; x<=X; ++x){
            if(mine[y][x] != 0){
                if(y-1 >=1 && y-1<=Y && x>=1 && x<=X){
                    if(mine[y-1][x] != 0){
                        adj[y][x].push_back(make_pair(y-1,x));
                        adj[y-1][x].push_back(make_pair(y,x));
                    }
                }
                if(y+1 >=1 && y+1<=Y && x>=1 && x<=X){
                    if(mine[y+1][x] !=0){
                        adj[y][x].push_back(make_pair(y+1,x));
                        adj[y+1][x].push_back(make_pair(y,x));     
                    }
                }

                if(y >=1 && y<=Y && x-1>=1 && x-1<=X){
                    if(mine[y][x-1] !=0){
                        adj[y][x].push_back(make_pair(y,x-1));
                        adj[y][x-1].push_back(make_pair(y,x));
                    }

                }

                if(y >=1 && y <=Y && x+1>=1 && x+1<=X){
                    if(mine[y][x+1] != 0){
                        adj[y][x].push_back(make_pair(y,x+1));
                        adj[y][x+1].push_back(make_pair(y,x));
                    }

                }
            }
        }
    }

    printf("%d",bfs(1,1));
}
Edit & run on cpp.sh
Jun 21, 2019 at 12:27pm
epdlqlemqpzja1234 (2)
Test Min Distance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include<iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

int MIN = 10000;
int Y;
int X;
int mine[100+10][100+10];
vector<pair<int, int>> adj[100+10][100+10];

int bfs(int y, int x)
{
    queue<pair<int, int>> que; 
    int visited[100+10][100+10]={0,};

    que.push(make_pair(y,x));
    visited[y][x] = 1;
    
    while(!que.empty()){
        pair<int,int> v = que.front();
        que.pop();
        
        if(v.first == Y && v.second == X){
            if(MIN > visited[v.first][v.second]){
                MIN = visited[v.first][v.second];
            }
        }

        for(size_t i=0; i<adj[v.first][v.second].size(); ++i){
            if(visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] == 0)
                que.push(make_pair(adj[v.first][v.second][i].first, adj[v.first][v.second][i].second));
                visited[adj[v.first][v.second][i].first][adj[v.first][v.second][i].second] = visited[v.first][v.second]+1;
                
        }
    }

    // for(int y=1; y<=Y; ++y){
    //     for(int x=1; x<=X; ++x){
    //         printf("%d ", visited[y][x]);
    //     }
    //     printf("\n");
    // }

    return MIN;
}

int main()
{
    scanf("%d %d", &Y, &X);
    for(int y=1; y<=Y ; ++y){
        for(int x=1; x<=X; ++x){
            scanf("%1d", &mine[y][x]);
        }
    }

    //make adjacent list
    for(int y=1; y<=Y; ++y){
        for(int x=1; x<=X; ++x){
            if(mine[y][x] != 0){
                if(y-1 >=1 && y-1<=Y && x>=1 && x<=X){
                    if(mine[y-1][x] != 0){
                        adj[y][x].push_back(make_pair(y-1,x));
                        adj[y-1][x].push_back(make_pair(y,x));
                    }
                }
                if(y+1 >=1 && y+1<=Y && x>=1 && x<=X){
                    if(mine[y+1][x] !=0){
                        adj[y][x].push_back(make_pair(y+1,x));
                        adj[y+1][x].push_back(make_pair(y,x));     
                    }
                }

                if(y >=1 && y<=Y && x-1>=1 && x-1<=X){
                    if(mine[y][x-1] !=0){
                        adj[y][x].push_back(make_pair(y,x-1));
                        adj[y][x-1].push_back(make_pair(y,x));
                    }

                }

                if(y >=1 && y <=Y && x+1>=1 && x+1<=X){
                    if(mine[y][x+1] != 0){
                        adj[y][x].push_back(make_pair(y,x+1));
                        adj[y][x+1].push_back(make_pair(y,x));
                    }

                }
            }
        }
    }

    printf("%d",bfs(1,1));
}
Edit & run on cpp.sh
Topic archived. No new replies allowed.