首页 > 代码库 > ZOJ 3781 Paint the Grid Reloaded (最短路)
ZOJ 3781 Paint the Grid Reloaded (最短路)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3781
题意：
在n*m矩阵的图定义连通区域为x值或y值相同且颜色相同的连通，连通具有传递性
每次可以把一个连通区域颜色反转(O变X,X变O)
问把所有块的颜色变为X最小的步数
方法：
很巧妙的最短路问题，先建图，然后以每个顶点为起点，找单源最短路的最大的值（也就是最深的深度），然后这个值取min
建图：相邻的块连边权1的边（即：通过1次反转可以使得两个连通块变为一个连通块）
注意：
floyd会TLE，需要邻接表建图
因为是稀疏图且边权为1，所以使用bfs或者spfa或者dijkstra均可
代码：spfa
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn = 1610; 23 const int maxm = 100010; 24 const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 char mtx[50][50]; 33 int label[50][50]; 34 int g[maxn][maxn]; 35 struct Edge 36 { 37 int u, v; 38 int w; 39 int next; 40 Edge(int _u = -1, int _v = -1, int _w = -1, int _next = -1): u(_u), v(_v), w(_w), next(_next) {} 41 } edge[maxm]; 42 int n; 43 int N, M; 44 int head[maxn]; 45 int d[maxn]; 46 int en; 47 int ans; 48 void addse(int u, int v, int w) 49 { 50 edge[en] = Edge(u, v, w, head[u]); 51 head[u] = en++; 52 } 53 void adde(int u, int v, int w) 54 { 55 addse(u, v, w); 56 addse(v, u, w); 57 } 58 void init() 59 { 60 memset(g, 0x3f, sizeof(g)); 61 memset(head, -1, sizeof(head)); 62 en = 0; 63 memset(label, -1, sizeof(label)); 64 ans = 0; 65 } 66 void input() 67 { 68 scanf("%d%d", &N, &M); 69 for (int i = 0; i < N; i++) 70 scanf("%s", mtx[i]); 71 } 72 void debug() 73 { 74 // 75 } 76 void dfs(int x, int y, char ch) 77 { 78 label[x][y] = n; 79 for (int i = 0; i < 4; i++) 80 { 81 int nx = x + P[i]; 82 int ny = y + Q[i]; 83 if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; 84 if (label[nx][ny] == -1 && mtx[nx][ny] == ch) 85 { 86 dfs(nx, ny, ch); 87 } 88 } 89 } 90 void build() 91 { 92 n = 0; 93 for (int i = 0; i < N; i++) 94 { 95 for (int j = 0; j < M; j++) 96 { 97 if (label[i][j] == -1) 98 { 99 dfs(i, j, mtx[i][j]);100 n++;101 }102 }103 }104 105 for (int i = 0; i < N; i++)106 {107 for (int j = 0; j < M; j++)108 {109 for (int p = 0; p < 4; p++)110 {111 int nx = i + P[p];112 int ny = j + Q[p];113 if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;114 g[label[i][j]][label[nx][ny]] = g[label[nx][ny]][label[i][j]] = 1;115 }116 }117 }118 119 for (int i = 0; i < n; i++)120 {121 for (int j = i + 1; j < n; j++)122 {123 if (g[i][j]==1)124 {125 adde(i, j, 1);126 // cout << j << " ";127 }128 }129 // cout << endl;130 }131 }132 int spfa(int s)133 {134 int cnt[maxn];135 int mark[maxn];136 queue<int> Q;137 for (int i = 0; i < n; ++i) d[i] = inf;138 memset(mark, 0, sizeof(mark));139 memset(cnt, 0, sizeof(cnt));140 d[s] = 0;141 Q.push(s);142 mark[s] = 1;143 cnt[s]++;144 while (Q.size())145 {146 int u = Q.front();147 Q.pop();148 mark[u] = 0;149 for (int i = head[u]; i != -1; i = edge[i].next)150 {151 int v = edge[i].v;152 int w = edge[i].w;153 if (d[u] + w < d[v])154 {155 d[v] = d[u] + w;156 if (mark[v] == 0)157 {158 mark[v] = 1;159 Q.push(v);160 if (++cnt[v] > n) return inf; //有负环，可以用DFS找161 }162 }163 }164 }165 int ret = -1;166 for (int i = 0; i < n; i++)167 {168 ret = max(ret, d[i]);169 }170 if (ret == -1) return inf;171 // cout<<"ret:"<<ret<<endl;172 return ret;173 }174 void solve()175 {176 build();177 178 ans = inf;179 for (int i = 0; i < n; i++)180 {181 ans = min(ans, spfa(i));182 }183 printf("%d\n", ans);184 }185 void output()186 {187 //188 }189 int main()190 {191 // std::ios_base::sync_with_stdio(false);192 #ifndef ONLINE_JUDGE193 freopen("in.cpp", "r", stdin);194 #endif195 196 int T;197 scanf("%d", &T);198 while (T--)199 {200 init();201 input();202 solve();203 output();204 }205 return 0;206 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。