¾¢ÎèÍÅ
°æÖ÷
  
UID 21313
¾«»ª
1
»ý·Ö 190
Ìû×Ó 180
ÔĶÁȨÏÞ 100
×¢²á 2006-4-19
״̬ ÀëÏß
|
ÊÔÌâÈý£¨15·Ö£©
¡¡¡¡
¡¡¡¡ÔĶÁÒÔÏÂ˵Ã÷ºÍÁ÷³Ìͼ£¬´Ó¹©Ñ¡ÔñµÄ´ð°¸ÖÐÑ¡³öÓ¦ÌîÈëÁ÷³Ìͼ __(n)__ ´¦µÄ×Ö¾äдÔÚ´ðÌâÖ½µÄ¶ÔÓ¦À¸ÄÚ¡£
¡¡¡¡
¡¡¡¡[˵Ã÷]
¡¡¡¡
¡¡¡¡Ò»¸öÓ¡Ë¢µç·°åµÄ²¼ÏßÇøÓò¿É·Ö³Én¡Ám¸ö·½¸ñ£¬Èçͼ3-1£¨a£©Ëùʾ£¬ÏÖÔÚÐèҪȷ¶¨µç·°åÖиø¶¨µÄÁ½¸ö·½¸ñµÄÖÐÐĵãÖ®¼äµÄ×î¶Ì²¼Ïß·½°¸¡£µç·ֻÄÜÑØË®Æ½»ò´¹Ö±·½Ïò²¼Ïߣ¬Èçͼ3-1£¨b£©ÖÐÐéÏßËùʾ¡£ÎªÁ˱ÜÃâÏß·Ïཻ£¬Ó¦½«ÒѲ¼¹ýÏߵķ½¸ñ×÷³É·âËø±ê¼Ç£¬ÆäËûÏß·²»ÔÊÐí´©¹ý±»·âËøµÄ·½¸ñ¡£
[ͼ3-1]
¡¡¡¡
¡¡
¡¡¡¡Éè¸ø¶¨Ó¡Ë¢µç·°åµÄÆðʼ·½¸ñxÓëÄ¿µÄ·½¸ñyÉÐδ²¼Ïߣ¬ÇóÕâÁ½¸ö·½¸ñ¼ä×î¶Ì²¼Ïß·½°¸µÄ»ù±¾Ë¼Â·ÊÇ£º´ÓÆðʼ·½¸ñx¿ªÊ¼£¬ÏÈ¿¼²é¾àÀëÆðʼ·½¸ñ¾àÀëΪkµÄijһ¸ö¿É´ï·½¸ñ¾ÍÊÇÄ¿±ê·½¸ñyʱΪֹ£¬»òÕßÓÉÓÚ²»´æÔÚ´Óxµ½yµÄ²¼Ïß·½°¸¶øÖÕÖ¹¡£²¼ÏßÇøÓòÖеÄÿһ¸ö·½¸ñÓëÆäÏàÁÚµÄÉÏ¡¢Ï¡¢×ó¡¢ÓÒËĸö·½¸ñÖ®¼äµÄ¾àÀëΪ1£¬ÒÀ´ÎÑØÏ¡¢ÓÒ¡¢ÉÏ¡¢×óÕâËĸö·½Ïò¿¼²é£¬²¢ÓÃÒ»¸ö¶ÓÁмǼ¿É´ï·½¸ñµÄλÖᣱí3-1¸ø³öÁËÑØÕâËĸö·½Ïòǰ½ø1²½Ê±Ïà¶ÔÓÚµ±Ç°·½¸ñµÄÏà¶ÔÆ«ÒÆÁ¿¡£
¡¡¡¡
¡¡¡¡[±í3-1]
¡¡¡¡
¡¡¡¡ËÑË÷˳Ðòi ·½Ïò ÐÐÆ«ÒÆÁ¿ ÁÐÆ«ÒÆÁ¿
¡¡¡¡
¡¡¡¡0 ÉÏ -1 0
¡¡¡¡
¡¡¡¡1 ÓÒ 0 1
¡¡¡¡
¡¡¡¡2 ÉÏ -1 0
¡¡¡¡
¡¡¡¡3 ×ó 0 -1
¡¡¡¡
¡¡¡¡ÀýÈ磬ÉèÓ¡Ë¢µç·°åµÄ²¼ÏßÇøÓò¿É»®·ÖΪһ¸ö6¡Á8µÄ·½¸ñÕóÁУ¬Èçͼ3-2£¨a£©Ëùʾ£¬ÆäÖÐÒõÓ°±íʾÒÑ·âËø·½¸ñ¡£´ÓÆðʼ·½¸ñx( λÖÃ[3£¬2]£¬±ê¼ÇΪ0)³ö·¢£¬°´ÕÕÏ¡¢ÓÒ¡¢ÉÏ¡¢×óµÄ·½ÏòÒÀ´Î¿¼²é£¬Ëù±ê¼ÇµÄ¿É´ï·½¸ñÈçͼ3-2£¨a£©Ëùʾ£¬Ä¿±ê·½¸ñΪy( λÖÃ[4£¬7]£¬±ê¼ÇΪ10)£¬ÏàÓ¦µÄ×î¶Ì²¼Ïß·¾¶Èçͼ3-2(b) ÐéÏßËùʾ¡£
¡¡¡¡
[ͼ3-2]
¡¡¡¡
¡¡
¡¡¡¡Í¼3-3ºÍͼ3-4ËùʾµÄÁ÷³Ìͼ¼´ÀûÓÃÉÏÊö˼Ïë·£¬Ôڵ緰巽¸ñÕóÁÐÖнøÐбê¼Ç£¬Í¼ÖÐʹÓõÄÖ÷Òª·ûºÅÈç±í3-2Ëùʾ¡£ÔÚͼ3-4ÖУ¬ÉèÖõç·°å³õʼ¸ñ¾Ö¼´½«¿É²¼Ïß·½¸ñÖÃΪÊýÖµ-1¡¢ÒѲ¼Ïß·½¸ñ£¨¼´·âËø·½¸ñ£©ÖÃΪ-9¡£ÉèÖ÷½¸ñÕóÁÐ"Χǽ"µÄÄ¿µÄÊÇÊ¡ÂÔ·½¸ñλÖõı߽çÌõ¼þÅж¨£¬·½·¨ÊÇÔÚËÄÖܸ½¼Ó¸ñ£¬²¢½«Æä±ê¼ÇΪ-9£¨Óë·âËø±ê¼ÇÏàͬ£©¡£
¡¡¡¡
¡¡¡¡[±í3-2]
¡¡¡¡
¡¡¡¡·ûºÅ º¬Òå
¡¡¡¡
¡¡¡¡Grid¡¡¡¡ È«¾Ö¶þάÊý×éGrid[N+2,M+2],±íʾµç·°å·½¸ñÕóÁУ¬³õʼʱÊý×éÔªËØGrid[i,j]rµÄֵΪ-1±íʾµ±Ç°·½¸ñ¿É²¼Ïߣ¬Îª-9±íʾǰ·½¸ñ²»¿É²¼Ïß¡£
¡¡¡¡
¡¡¡¡Offset¡¡¡¡Ò»Î¬Êý×éoffset[4] ffset(0¡Üi¡Ü3)µÄ·ÖÁ¿Îªr£¨ÐÐÆ«ÒÆÁ¿£©ºÍc(ÁÐÆ«ÒÆÁ¿)£¬°´ÕÕ±í3-1µÄÄÚÈÝÉèÖÃÆäÖµ¡£
¡¡¡¡
¡¡¡¡Startpos¡¢Endpos¡¢Curpos¡¢T ·Ö±ð±íʾÆðʼ·½¸ñ¡¢Ä¿±ê·½¸ñ¡¢µ±Ç°·½¸ñºÍÁÙʱ·½¸ñ£¬ÆäλÖÃÓ÷ÖÁ¿¶ÈrowºÍcolÈ·¶¨¡£
¡¡¡¡
¡¡¡¡Q.insert(s) ½«·½¸ñsµÄλÖÃÐÅÏ¢¼ÓÈë¶ÓÁÐ
¡¡¡¡
¡¡¡¡Q.delete() ɾ³ý·Ç¿Õ¶ÓÁеĶÓÍ·ÔªËØ£¬²¢·µ»Ø¸ÃÔªËØ¡£
¡¡¡¡
¡¡¡¡Q.empty() Èô¶ÓÁÐQΪ¿Õ£¬Ôò·µ»Øtrue;·ñÔò·µ»Øfalse¡£
¡¡¡¡
¡¡¡¡
[ͼ3-3]
¡¡¡¡
¡¡
¡¡¡¡
[ͼ3-4]
¡¡¡¡

¡¡¡¡
¡¡¡¡¡ñ¹©Ñ¡ÔñµÄ´ð°¸
¡¡¡¡[a] Found¡Ùtrue¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ Found = true
¡¡¡¡[c] T = EndPos¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ [d] Q.insert(T)
¡¡¡¡[e] T ¡û Q.delete()¡¡¡¡¡¡¡¡¡¡¡¡[f] CurPos = EndPos
¡¡¡¡[g] i¡Ý4¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ [h] CurPos ¡û Q.delete()
¡¡¡¡ Grid[T.row,T.col] = -1¡¡¡¡ [j] Grid[T.row,T.col]¡Ù-1
|
|