이 문제는 n,m이 100 이하인 짝수인데, 1502번은 n,m이 8 이하인 짝수에요.

전 1502번은 풀었고, 9021번은 잘 모르겠어서 함께 고민해보면 좋겠다싶어서 글을 올립니다! ㅎㅎ

우선 제가 생각했던 것들과 힌트받았던 것들을 요약하면,

1) n,m이 모두 짝수이므로 시작점과 도착점의 좌표 (xs, ys)와 (xe, ye)가 있을 때, 답이 존재하려면 반드시 xs+ys+xe+ye가 홀수여야합니다. 전 규칙을 찾다가 우연히 알게되었는데... @pichulia 님의 설명을 빌려쓰면, 그리드를 흰색, 검은색이 나뉘어져있는 체스판으로 생각했을 때, "흰색->검은색->흰색->...->검은색" 이거나 그 반대가 되어야하기 때문입니다. 같은 색으로 경로가 끝난다면 n*m도 짝수라는 가정에 모순이 되기 때문이죠.

2) n이 작은 경우(8 이하)는 dfs로 되지만 큰 경우 안됩니다.

3) 1)번 조건을 만족한다고 무조건 해가 있는 것이 아닙니다.

4) 그리드에서 시작점과 도착점을 기준으로 각각 수평,수직으로 선을 그으면, 9개의 영역으로 나뉘어지더라구요. 각 영역 안에서 ㄹ자 비슷한 형태로 매꿀 수 있지 않을까 생각합니다.