#include <bits/stdc++.h>
using namespace std;
const int MAXN=4e3+5;
char v[MAXN][MAXN];
vector<int> g[MAXN*MAXN], pes[MAXN*MAXN];
int dist[MAXN];
int n, m;
int convert(int i, int j) { if(i==0||j==0) return 0; return (i-1)*m+j; }
void liga(int i, int j, int i2, int j2){
if(i<=0||j<=0||i>n||j>m) return;
if(i2<=0||j2<=0||i2>n||j2>m) return;
if(v[i][j]=='.'||v[i2][j2]=='.') return;
int a=convert(i, j); int b=convert(i2, j2);
g[a].push_back(b);
int peso=0;
if(v[i][j]!=v[i2][j2]) peso=1;
pes[a].push_back(peso);
// printf("liga %d e %d - %d\n", a, b, peso);
}
void bfs() {
memset(dist, -1, sizeof(dist));
dist[1]=1;
deque<int> dq;
dq.push_back(1);
while(!dq.empty()) {
int cur=dq.front(); dq.pop_front();
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; int peso=pes[cur][i];
if(dist[viz]!=-1) continue;
if(peso==0) dq.push_front(viz);
else dq.push_back(viz);
dist[viz]=dist[cur]+peso;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++) scanf(" %s", &v[i][1]);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
int cur=convert(i, j);
liga(i, j, i-1, j);
liga(i, j, i+1, j);
liga(i, j, i, j-1);
liga(i, j, i, j+1);
}
}
bfs();
int resp=1;
for(int i=1; i<=n*m; i++) resp=max(resp, dist[i]);
// for(int i=1; i<=n; i++) {
// for(int j=1; j<=m; j++) {
// printf("%d ", dist[convert(i, j)]);
// }
// printf("\n");
// }
printf("%d\n", resp);
}
Compilation message
tracks.cpp: In function 'void bfs()':
tracks.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
tracks.cpp: In function 'int main()':
tracks.cpp:46:8: warning: unused variable 'cur' [-Wunused-variable]
int cur=convert(i, j);
^~~
tracks.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=n; i++) scanf(" %s", &v[i][1]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
454720 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2083 ms |
554432 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2052 ms |
624360 KB |
Time limit exceeded |
| 4 |
Incorrect |
1163 ms |
765424 KB |
Output isn't correct |
| 5 |
Incorrect |
696 ms |
756208 KB |
Output isn't correct |
| 6 |
Correct |
724 ms |
753804 KB |
Output is correct |
| 7 |
Correct |
736 ms |
754120 KB |
Output is correct |
| 8 |
Incorrect |
765 ms |
754272 KB |
Output isn't correct |
| 9 |
Incorrect |
743 ms |
754364 KB |
Output isn't correct |
| 10 |
Incorrect |
762 ms |
756600 KB |
Output isn't correct |
| 11 |
Incorrect |
784 ms |
757088 KB |
Output isn't correct |
| 12 |
Incorrect |
764 ms |
760224 KB |
Output isn't correct |
| 13 |
Incorrect |
741 ms |
756352 KB |
Output isn't correct |
| 14 |
Incorrect |
703 ms |
756312 KB |
Output isn't correct |
| 15 |
Incorrect |
762 ms |
767428 KB |
Output isn't correct |
| 16 |
Incorrect |
809 ms |
770616 KB |
Output isn't correct |
| 17 |
Incorrect |
774 ms |
762588 KB |
Output isn't correct |
| 18 |
Incorrect |
737 ms |
765432 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
701 ms |
769748 KB |
Output isn't correct |
| 2 |
Incorrect |
973 ms |
801268 KB |
Output isn't correct |
| 3 |
Execution timed out |
2092 ms |
948580 KB |
Time limit exceeded |
| 4 |
Incorrect |
1094 ms |
801096 KB |
Output isn't correct |
| 5 |
Execution timed out |
2133 ms |
1023700 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2132 ms |
1022624 KB |
Time limit exceeded |
| 7 |
Incorrect |
722 ms |
770396 KB |
Output isn't correct |
| 8 |
Incorrect |
710 ms |
769728 KB |
Output isn't correct |
| 9 |
Incorrect |
678 ms |
755576 KB |
Output isn't correct |
| 10 |
Incorrect |
750 ms |
754332 KB |
Output isn't correct |
| 11 |
Incorrect |
751 ms |
769620 KB |
Output isn't correct |
| 12 |
Incorrect |
750 ms |
755140 KB |
Output isn't correct |
| 13 |
Incorrect |
998 ms |
801016 KB |
Output isn't correct |
| 14 |
Incorrect |
978 ms |
782072 KB |
Output isn't correct |
| 15 |
Incorrect |
781 ms |
776668 KB |
Output isn't correct |
| 16 |
Incorrect |
841 ms |
778036 KB |
Output isn't correct |
| 17 |
Incorrect |
1442 ms |
869268 KB |
Output isn't correct |
| 18 |
Incorrect |
1176 ms |
834912 KB |
Output isn't correct |
| 19 |
Incorrect |
1107 ms |
801080 KB |
Output isn't correct |
| 20 |
Incorrect |
1059 ms |
819948 KB |
Output isn't correct |
| 21 |
Incorrect |
1624 ms |
917968 KB |
Output isn't correct |
| 22 |
Execution timed out |
2145 ms |
1049600 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2105 ms |
974664 KB |
Time limit exceeded |
| 24 |
Incorrect |
1837 ms |
962888 KB |
Output isn't correct |
| 25 |
Execution timed out |
2029 ms |
1049600 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2153 ms |
1028336 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2109 ms |
1008376 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2125 ms |
1029724 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2115 ms |
1049604 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2125 ms |
1015048 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2100 ms |
1031392 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2145 ms |
1012584 KB |
Time limit exceeded |
