Submission #1065066

#TimeUsernameProblemLanguageResultExecution timeMemory
1065066Dennis_JasonMaze (JOI23_ho_t3)C++14
0 / 100
2089 ms452 KiB
#include <bitset> #include <cmath> #include <functional> #include <algorithm> #include <numeric> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <iterator> #include <limits> #include <list> #include <map> #include <unordered_map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <cstring> #include <climits> #define pb push_back #define MOD 1000000007 #define NMAX 6000001 #define nl '\n' #define INF 1000000007 #define pii1 pair<int, pair<int,int>> (1,(1,2)); #define pii pair<int,int> #define tpl tuple<int,int,int,int,int> using namespace std; ifstream fin("data.in"); ofstream fout("data.out"); /* ====================DEMONSTRATION====================== n=2 1....#####..## ....########## ####.......... ##########.... ##########.... 1....####....# =========================END=========================== */ int r,c,n; int x,y,a,b,node_s,node_f; int di[]={1,-1,0,0}; int dj[]={0,0,1,-1}; int **mat,**cost; bool **vis; bool inmat(int i,int j) { return i>=1 && i<=r && j>=1 && j<=c; } void dfs(int i,int j,int c,int o,int p) { vis[i][j]=1; for(int d=0;d<4;++d) { int inou=di[d]+i; int jnou=dj[d]+j; if(inmat(inou,jnou) && cost[inou][jnou]>c ) { if(mat[inou][jnou]==0) { cost[inou][jnou]=min(cost[inou][jnou],c); dfs(inou,jnou,c,o,p); // dfs(inou,jnou,c+1,inou,jnou); } else if(mat[inou][jnou]==1 && (abs(inou-o)+abs(jnou-p)+1)<=n) { cost[inou][jnou]=min(cost[inou][jnou],c); dfs(inou,jnou,c,o,p); // cout<<inou<<" "<<jnou<<"----"<<o<<" "<<p<<nl; // dfs(inou,jnou,c+1,inou,jnou); } else { cost[inou][jnou]=min(cost[inou][jnou],c+1); dfs(inou,jnou,c+1,inou,jnou); } } } } signed main() { cin>>r>>c>>n; mat= new int*[r+1]; for(int i=1;i<=r;++i) mat[i]=new int[c+1]; cost= new int*[r+1]; for(int i=1;i<=r;++i) cost[i]=new int[c+1]; vis=new bool*[r+1]; for(int i=1;i<=r;++i) vis[i]=new bool[c+1]; cin>>x>>y; cin>>a>>b; for(int i=1;i<=r;++i) { for(int j=1;j<=c;++j) { cost[i][j]=INF; char x; cin>>x; if(x=='.') mat[i][j]=0; else mat[i][j]=1; } } dfs(x,y,0,INF,INF); cout<<cost[a][b]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...