問題描述
Given an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.
給一個(gè)MxN的矩陣，問能不能找到一條一筆畫的路徑戒财，能不重復(fù)地通過每個(gè)節(jié)點(diǎn)而且開始和結(jié)束的點(diǎn)相鄰。
信息補(bǔ)全
好像沒什么需要詢問補(bǔ)充的堪置。
問題分析
1x1的時(shí)候因?yàn)闆]有結(jié)束點(diǎn)，因此是不符合要求的。
暴力破解
完全不管三七二十一，就用程序來模擬。
那么首先是要選擇出發(fā)點(diǎn)吧蜀撑，有MxN種選擇粪摘。
然后是生成路徑椎咧，可以考慮BFS或者DFS向臀。
在無路可走的時(shí)候判斷一下是不是走完了芹彬，以及是不是和初始點(diǎn)相鄰会前。
此外還可以每一步判斷一下初始點(diǎn)周圍還有沒有位置好乐。
不過總的來說時(shí)間復(fù)雜度非常高蔚万。
觀察法
其實(shí)這個(gè)題更多是智力向或者數(shù)學(xué)向，觀察歸納會比較有效假夺。假設(shè)N>0.
- 1xN
這種情況，只有1x2是符合條件的已卷。但其實(shí)還是托了那個(gè)2的福梧田。 - 2xN
這種情況都符合。從第一排的第一個(gè)點(diǎn)往這一排末端走侧蘸，到頭拐個(gè)彎回來裁眯，就是U字形的路線。 - 3xN
考慮3x3讳癌，無論如何也無法做到穿稳。 - 4xN
考慮4x3描验，凹字形路線也是可以的匹摇。
觀察了這么多盐碱，其實(shí)可以看出一點(diǎn)規(guī)律了锣杂。
也就是說如果MN中有一個(gè)偶數(shù)吸奴，就可以符合骡尽。
為什么患亿？之前已經(jīng)知道對于2的情況使用U字形路線慌核，其實(shí)那是凹的特例娩怎。凹字折返回來要求就是偶數(shù)搔课。
考慮大于等于4的偶數(shù)情況，假設(shè)有N列截亦，N是偶數(shù)爬泥，然后從左上角出發(fā)向下，觸底之后折返崩瓤，到差一行的時(shí)候再往右一格再往下袍啡。
這個(gè)路線下是無視M的值的，因?yàn)椴挥绊憽?br>
假如MN都是奇數(shù)却桶，到最后一列是往下走境输，回不來蔗牡。
因此，差不多就能得到結(jié)論了：當(dāng)MN全部為奇數(shù)時(shí)嗅剖，返回否辩越。其他情況返回是。
從另一個(gè)角度來看信粮，題目要求的路線一定會經(jīng)過偶數(shù)個(gè)格子黔攒，因此MxN為奇數(shù)時(shí)不符合。
能不能證明那種路線一定會經(jīng)過偶數(shù)格子强缘？不會證明督惰。
代碼
略
總結(jié)
面試時(shí)要想證明結(jié)論的正確性，可能難度比較大旅掂，需要數(shù)學(xué)功底赏胚。
