I will keep a record of the problems that I made a mistake in the past questions of AtCoder and the problems that left an impression on me.
3RE
I made a lot of silly mistakes, so I was rushing to solve it.
The basic policy is that when changing the number of $ A_ {i, j} $ to 1, it takes time to find the minimum magical power to change that number to 1, so first apply each minimum magical power to the WF method. It is a policy to ask for it using.
I felt growth up to the point where I came up with the minimum magical power (while changing the numbers) → WF method, but when I rewrote it, I made a mistake in the index value and it became RE. It was. ** (I changed the place to j to i.)
Furthermore, if you write like [] * n **, you will not notice that each array points to the same object **, you will make a mistake at the time of input, and it will take time to debug there. I have.
answerD.py
dp=[[0 for j in range(10)] for i in range(10)]
h,w=map(int,input().split())
for i in range(10):
s=list(map(int,input().split()))
for j in range(10):
dp[i][j]=s[j]
#The image of the WF method is to consider the shortest time without going through others, increase the places that can be passed from there, and take min more and more.
for k in range(10):
for i in range(10):
for j in range(10):
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
c=0
for i in range(h):
s=list(map(int,input().split()))
for j in range(w):
#I made a mistake in the subscript here
if s[j]!=-1 and s[j]!=1:
c+=dp[s[j]][1]
print(c)
I was addicted to it like never before, so I learned a lot at the same time as I withered.
This problem can be solved by ** thinking about the pattern that can be reached in the shortest time from the start point (1,1) to the end point (H, W) **. (It's a little difficult to come up with this idea ??)
Specifically, we implemented it by going to the four adjacent squares that can be reached from the square at that time and updating the information of the squares that arrived. Also, since what we want to find is a pattern that can be reached in the shortest time, if it is not the shortest from the start point, we devised a way to reduce the amount of calculation by stopping the recursion there without updating the square information.
It wasn't difficult as long as I came up with a method, but it seems that my method wasn't the best, and in Python ** recursion was too deep and it became RE **. (It was my first experience. In the case of RE, I thought it was an out-of-array reference.)
I checked here ** It seems that the depth of recursion is fixed in each environment in Python **, so the `setrecursionlimit``` function of the sys module (the function that sets the depth of recursion) Was used. I defined the depth of recursion by myself with the `setrecursionlimit``` function and forced to exit when it was about to exceed that depth.
Also, I didn't want to solve it with this solution, so when I rewrote it in C ++, I was able to AC without setting the depth of recursion. (Also, I learned here that you can ** a <= x <= b in Python but not in C ++ **.)
answerD.py
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())
def go_next(I,J,n):
n+=1
global dp,w,h
if n>1000:
return
if I<h-1:
if x[I+1][J]=="." and dp[I+s1][J]>dp[I][J]+1:
dp[I+1][J]=dp[I][J]+1
go_next(I+1,J,n)
if 0<I:
if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
dp[I-1][J]=dp[I][J]+1
go_next(I-1,J,n)
if J<w-1:
if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
dp[I][J+1]=dp[I][J]+1
go_next(I,J+1,n)
if 0<J:
if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
dp[I][J-1]=dp[I][J]+1
go_next(I,J-1,n)
x=[]
for i in range(h):
x.append(list(input()))
#print(x)
c=0
for i in range(h):
for j in range(w):
if x[i][j]==".":
c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
#Consideration when you cannot reach
if dp[h-1][w-1]==10000000000:
print(-1)
else:
print(c-dp[h-1][w-1])
answerD.cc
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef vector< vector<int> > vv;
#define INF 1e9
void go_next(int I,int J,vv& dp,vector<string> x,int w,int h){
if(I<h-1){
if(x[I+1][J]=='.' and dp[I+1][J]>dp[I][J]+1){
dp[I+1][J]=dp[I][J]+1;go_next(I+1,J,dp,x,w,h);
}
}
if(0<I){
if(x[I-1][J]=='.' and dp[I-1][J]>dp[I][J]+1){
dp[I-1][J]=dp[I][J]+1;go_next(I-1,J,dp,x,w,h);
}
}
if(J<w-1){
if(x[I][J+1]=='.' and dp[I][J+1]>dp[I][J]+1){
dp[I][J+1]=dp[I][J]+1;go_next(I,J+1,dp,x,w,h);
}
}
if(0<J){
if(x[I][J-1]=='.' and dp[I][J-1]>dp[I][J]+1){
dp[I][J-1]=dp[I][J]+1;go_next(I,J-1,dp,x,w,h);
}
}
}
int main(){
int h ,w;cin >> h >> w;
vv dp(h,vector<int>(w,INF));dp[0][0]=1;
vector<string> x(h);for(int i=0;i<h;i++)cin >>x[i];
int c=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(x[i][j]=='.'){c+=1;}
}
}
go_next(0,0,dp,x,w,h);
if(dp[h-1][w-1]==INF)cout << -1 << endl;
else cout << c-dp[h-1][w-1] << endl;
}
Recommended Posts