이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<deque>
using namespace std;
int n,m;
char mat[4001][4001];
int dirlin[4]={1,-1,0,0};
int dircol[4]={0,0,1,-1};
deque<int> dqlin;
deque<int> dqcol;
int best[4001][4001];
bool good(int lin, int col)
{
if(lin>=1 && lin<=n && col>=1 && col<=m)
return 1;
return 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{cin>>mat[i][j];best[i][j]=4000*4000+100;}
dqlin.push_back(1);
dqcol.push_back(1);
best[1][1]=1;
int lin,col;
while(dqlin.empty()==0)
{
lin=dqlin.front();
col=dqcol.front();
dqlin.pop_front();
dqcol.pop_front();
for(int i=0;i<4;i++)
{
if(good(lin+dirlin[i], col+dircol[i]) && mat[lin+dirlin[i]][col+dircol[i]]!='.' && best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])<best[lin+dirlin[i]][col+dircol[i]])
{
best[lin+dirlin[i]][col+dircol[i]]=best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]);
if(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])
{
dqlin.push_back(lin+dirlin[i]);
dqcol.push_back(col+dircol[i]);
}
else
{
dqlin.push_front(lin+dirlin[i]);
dqcol.push_front(col+dircol[i]);
}
}
}
}
int mxm=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(mat[i][j]!='.')
mxm=max(mxm,best[i][j]);
}
cout<<mxm;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |