BFS与DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

 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

#include<bits/stdc++.h>
using namespace std;
const int N = 55,M=N*N;
int g[N][N];
int cnt,maxarea;
bool st[N][N];
int m,n;
typedef pair<int,int> PII;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
/*
acwing 1098
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

5
9
*/ 
int bfs(int i,int j){
	int area = 0;
	queue<PII> q;
	q.push({i,j});
	st[i][j]=true;
	while(q.size()){
		PII t = q.front();
		q.pop();
		int a = t.first,b=t.second;
		area++;
		for(int k=0;k<4;k++){
			int x = a+dx[k],y=b+dy[k];
			if(x>=0&&x<m&&y>=0&&y<n&&!st[x][y]&&!(g[a][b]>>k&1)){
				st[x][y]=true;
				q.push({x,y});
			}
		}
	}
	return area;
}
int main(){
	cin>>m>>n;
	for(int i =0;i<m;i++){
		for(int j =0;j<n;j++){
			cin>>g[i][j];
		}
	}
	for(int i =0;i<m;i++){
		for(int j =0;j<n;j++){
			if(!st[i][j]){	
				maxarea=max(maxarea,bfs(i,j));			
				cnt++;				
			}
			
		}
	}
	cout<<cnt<<endl;
	cout<<maxarea<<endl;
	return 0;
} 

 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

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int,int> pii;
int g[N][N],d[N][N];
int n,m;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
queue<pii> que;
/*
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

8
*/ 
int dfs(){
	que.push({0,0});
	d[0][0] = 0;
	while(que.size()){
		pii t = que.front();
		que.pop();
		int a = t.first,b=t.second;
		for(int i = 0;i<4;i++){
			int x = a+dx[i];
			int y = b+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
				que.push({x,y});
				d[x][y] = d[a][b]+1;
			}
		}
	}
	return d[n-1][m-1];
}
int main(){
	cin>>n>>m;
	for(int i = 0;i<n;i++){
		for(int j =0;j<m;j++){
			cin>>g[i][j]; 
		}
	}
	memset(d,-1,sizeof d);
	cout<<dfs()<<endl;
	return 0;
}
 

 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

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
int dist[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
typedef pair<int,int> PII;
int n,m;
/*
3 4
0001
0011
0110

3 2 1 0
2 1 0 0
1 0 0 1
*/
void bfs(){
	memset(dist,-1,sizeof dist);
	queue<PII> q;
	for(int i =0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='1') q.push({i,j}),dist[i][j]=0;
		}
	}
	while(q.size()){
		PII t = q.front();
		q.pop();
		int a = t.first,b=t.second;
		for(int i=0;i<4;i++){
			int x = a+dx[i],y=b+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&dist[x][y]==-1){
				dist[x][y]=dist[a][b]+1;
				q.push({x,y});
			}
		} 
	}
}
int main(){
	cin>>n>>m;
	for(int i =0;i<n;i++) cin>>g[i];
	for(int i =0;i<n;i++){
		for(int j=0;j<m;j++){
			bfs();
		}
	}
	for(int i =0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<dist[i][j]<<" ";
		}
		puts(" ");
	}
	return 0;
}

 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

// 非常类似于dijskra
#include <iostream>
#include <cstring>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 550;

int n, m;  // 方格的数量为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[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};  // 相邻的四个格点
    int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};  // 与当前格点相邻的四个方格
    
    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];  // 考察与当前格点相邻的第i个方格
            int w = (g[ca][cb] != cs[i]);  // 不能导通，需要旋转一次
            int d = dist[t.x][t.y] + w;
            
            // 因为某个格点可能入队多次，需要更新dist[a][b]，更新后的数据需要入队
            if (d < dist[a][b]) {
                dist[a][b] = d;
                if (w) 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]);
        
        if ((n + m) & 1) puts("NO SOLUTION");
        else printf("%d\n", bfs());
    }
    
    return 0;
}