#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<ll,ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
const int INF = 1e9;
using namespace std;
const int MAXN = 4000*4000+500;
vector<ii> g[MAXN];
char grid[4000][4000];
int n,m;
inline int cost(char c1,char c2){
return (c1 == '.' or c2 == '.')?-1:(1-(c1==c2));
}
int dist[MAXN];
bool vis[MAXN];
inline int change(int i,int j){
return i*m+j;
}
inline void insertEdge(int a,int b,int c,vector<ii>& v){
v.pb({b,c});
}
inline void getEdges(int i,int j,vector<ii>& v){
if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){
insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]),v);
}
if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]),v);
}
if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){
insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]),v);
}
if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){
insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]),v);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
string s;
FOR(i,n){
cin >> s;
FOR(j,m)grid[i][j] = s[j];
}
/*
FOR(i,n){
FOR(j,m){
if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){
insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]));
}
if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]));
}
if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){
insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]));
}
if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){
insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]));
}
}
}*/
FOR(i,MAXN)dist[i] = INF;
queue<ii> q1;
queue<ii> q2;
q1.push({0,0});
while(1){
if(q1.empty() and q2.empty())break;
if(q1.empty())swap(q1,q2);
auto e = q1.front();q1.pop();
if(vis[e.ss])continue;
vis[e.ss] = 1;
dist[e.ss] = e.ff;
vector<ii> v;
//getEdges(e.ss/m,e.ss%m,v);
int i = e.ss/m;
int j = e.ss%m;
if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){
insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]),v);
}
if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]),v);
}
if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){
insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]),v);
}
if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){
insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]),v);
}
for(auto f : v){
if(dist[f.ff] <= dist[e.ss]+f.ss)continue;
if(f.ss == 0){
q1.push({e.ff,f.ff});
}else{
q2.push({e.ff+1,f.ff});
}
//pq.push({dist[e.ss]+f.ss,f.ff});
}
}/*
while(!pq.empty()){
auto e = pq.front();pq.pop();
if(dist[e.ss] <= e.ff)continue;
dist[e.ss] = e.ff;
vector<ii> v;
getEdges(e.ss/m,e.ss%m,v);
for(auto f : v){
if(dist[f.ff] <= dist[e.ss]+f.ss)continue;
pq.push({dist[e.ss]+f.ss,f.ff});
}
}*/
//return 0;
int mx = 0;
FOR(i,n){
FOR(j,m){
if(grid[i][j] != '.'){
mx = max(mx,dist[change(i,j)]);
}
// cout << setw(10) <<dist[change(i,j)] << " ";
}
//cout << endl;
}
cout << (mx + 1) << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
497 ms |
441448 KB |
Output is correct |
2 |
Correct |
395 ms |
438776 KB |
Output is correct |
3 |
Correct |
388 ms |
438964 KB |
Output is correct |
4 |
Correct |
445 ms |
441412 KB |
Output is correct |
5 |
Correct |
394 ms |
440056 KB |
Output is correct |
6 |
Correct |
403 ms |
438844 KB |
Output is correct |
7 |
Correct |
396 ms |
438920 KB |
Output is correct |
8 |
Correct |
396 ms |
438908 KB |
Output is correct |
9 |
Correct |
381 ms |
439092 KB |
Output is correct |
10 |
Correct |
417 ms |
440056 KB |
Output is correct |
11 |
Correct |
417 ms |
439776 KB |
Output is correct |
12 |
Correct |
485 ms |
440184 KB |
Output is correct |
13 |
Correct |
405 ms |
440064 KB |
Output is correct |
14 |
Correct |
403 ms |
440232 KB |
Output is correct |
15 |
Correct |
441 ms |
441216 KB |
Output is correct |
16 |
Correct |
472 ms |
441352 KB |
Output is correct |
17 |
Correct |
429 ms |
441092 KB |
Output is correct |
18 |
Correct |
486 ms |
441484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
440 ms |
453812 KB |
Output is correct |
2 |
Correct |
607 ms |
446692 KB |
Output is correct |
3 |
Correct |
1264 ms |
485864 KB |
Output is correct |
4 |
Correct |
562 ms |
453496 KB |
Output is correct |
5 |
Correct |
999 ms |
468260 KB |
Output is correct |
6 |
Execution timed out |
2052 ms |
508548 KB |
Time limit exceeded |
7 |
Correct |
422 ms |
454520 KB |
Output is correct |
8 |
Correct |
425 ms |
453752 KB |
Output is correct |
9 |
Correct |
371 ms |
439032 KB |
Output is correct |
10 |
Correct |
390 ms |
438776 KB |
Output is correct |
11 |
Correct |
429 ms |
454136 KB |
Output is correct |
12 |
Correct |
397 ms |
439392 KB |
Output is correct |
13 |
Correct |
591 ms |
446704 KB |
Output is correct |
14 |
Correct |
500 ms |
444092 KB |
Output is correct |
15 |
Correct |
461 ms |
444664 KB |
Output is correct |
16 |
Correct |
531 ms |
441720 KB |
Output is correct |
17 |
Correct |
868 ms |
454704 KB |
Output is correct |
18 |
Correct |
655 ms |
454384 KB |
Output is correct |
19 |
Correct |
620 ms |
453580 KB |
Output is correct |
20 |
Correct |
619 ms |
452436 KB |
Output is correct |
21 |
Correct |
930 ms |
469240 KB |
Output is correct |
22 |
Correct |
957 ms |
468128 KB |
Output is correct |
23 |
Correct |
1152 ms |
464052 KB |
Output is correct |
24 |
Correct |
750 ms |
468948 KB |
Output is correct |
25 |
Correct |
1605 ms |
485792 KB |
Output is correct |
26 |
Execution timed out |
2050 ms |
476392 KB |
Time limit exceeded |
27 |
Execution timed out |
2055 ms |
487960 KB |
Time limit exceeded |
28 |
Execution timed out |
2064 ms |
508716 KB |
Time limit exceeded |
29 |
Execution timed out |
2045 ms |
506776 KB |
Time limit exceeded |
30 |
Execution timed out |
2037 ms |
510976 KB |
Time limit exceeded |
31 |
Execution timed out |
2050 ms |
473320 KB |
Time limit exceeded |
32 |
Execution timed out |
2067 ms |
488284 KB |
Time limit exceeded |